基于MapReduce的连续SkyIine查询

doi:10.3969/j.issn.1000-0801.2014.05.014

摘要/Abstract

摘要：

随着Web网络和无线传感器网络的不断发展，大数据的出现对数据查询和处理产生了挑战。研究了MapReduce框架下移动对象的并行Skyline计算问题，采用基于角度划分的方法解决负载平衡问题，并提出了一种过滤策略进行剪枝提高计算效率，在此基础上分别实现了静态Skyline算法和基于事件跟踪的MR-Track算法。最后通过对比实验验证了算法的有效性。

关键词: Skyline查询, MapReduce, Hadoop, 移动对象, 连续查询

Abstract:

With the development of Web and wireless sensor networks, the appearance of big data has brought a great challenge to data query and process. The parallel Skyline computing issue of a moving query object under the MapReduce framework was studied. To solve the problem of load balance, a method based on angle partition was adopted. Then a filtering method was introduced to improve the efficiency. On the basis of those methods, a static Skyline algorithm and an event tracking algorithm named MR-Track were implemented respectively. Finally, many experiments were made to verify the effective and efficient of MR-Track algorithm.

Key words: Skyline query, MapReduce, Hadoop, moving object, continuous query

单观敏,董一鸿,何贤芒. 基于MapReduce的连续SkyIine查询[J]. 电信科学, 2014, 30(5): 94-104.

Guanmin Shan,Yihong Dong,Xianmang He. Continuous Skyline Queries Based on MapReduce[J]. Telecommunications Science, 2014, 30(5): 94-104.

图/表 11

图1

表1

图2

图3

图4

图5

图6

图7

图8

图9

图10

参考文献 19

1	Borzsonyi S , Kossmann D , Stocker K . The Skyline operator. Proceedings of the International Conference on Data Engineering （ICDE）, Heidelberg, Germany, 2011: 421～430
2	Dean J , Ghemawat S . MapReduce: simplified data processing on large clusters. Communications of the ACM, 2005,51（1）: 107～113
3	Tan K L , Eng P K , Ooi B C . Efficient progressive skyline computation. Proceedings of the VLDB, Roma,Italy, 2001: 301～310
4	Kossmann D , Ramsak F , Rost S . Shooting stars in the sky: an online algorithm for skyline queries. Proceedings of the Very Large Data Bases（VLDB）, Hong Kong, China, 2002: 275～286
5	Papadias D , Tao Y F , Fu G , et al. An optimal and progressive algorithm for skyline queries. Proceedings of ACM Management of Data（SIGMOD）, California, USA, 2003: 467～478
6	Balke W T , Güntzer U , Zheng J X . Efficient distributed Skylining for web information systems. Proceedings of International Conference on Extending Database Technology （EDBT）, Heraklion, Crete, Greece, 2004: 256～273
7	Cui B , Lu H , Xu Q Q , et al. Parallel distributed processing of constrained Skyline queries by ltering. Proceedings of International Conference on Data Engineering（ICDE）, Cancun, Mexico, 2008: 546～555
8	Huang Z Y , Lu H , Ooi B C , et al. Continuous skyline queries for moving objects. IEEE Transactions on Knowledge and Data Engineering, 2006,18（12）: 1645～1658
9	Tian L , Wang L , Zou P , et al. Continuous monitoring of skyline 9 Tian L, Wang L, Zou P, et al. Continuous monitoring of skyline
10	付世昌，董一鸿，唐燕琳等. 基于事件的位置不确定移动对象连续概率Skyline查询．自动化学报， 2011,37（7）: 836～848
11	Vlachou A , Doulkeridis C , Kotidis Y . Angle-based space partitioning for efficient parallel skyline computation. Proceedings of ACM Management of Data （SIGMOD）, Vancouver, BC, Canada, 2008: 227～238
12	Park S , Kim T , Park J , et al. Parallel skyline computation on multicore architectures. Proceedings of IEEE 25th International Conference on Date of Conference （ICDE）, Shanghai, China, 2009: 760～771
13	Kohler H , Yang J , Zhou X F . Efficient parallel skyline processing using hyperplane projections. Proceedings of the ACM SIGMOD International Conference on Management of Data, Athens, Greece, 2011: 85～96
14	张波良，周水庚，关佶红 . MapReduce框架下的Skyline计算．计算机科学与探索， 2011,5（5）: 385～397
15	Chen L , Hwang K , Wu J . MapReduce Skyline query processing with a new angular partitioning approach. Proceedings of Parallel and Distributed Processing Symposium Workshops ＆ PhD Forum （IPDPSW）, Shanghai, China, 2012: 2262～2270
16	丁琳琳，信俊昌，王国仁 . 基于MapReduce的海量数据高效Skyline查询处理．计算机学报， 2011,34（10）: 1785～1796
17	雷婷，王涛，曲武等. 云环境下基于超球面投影分区的Skyline计算．计算机科学， 2013,40（6）: 164～171
18	Xiao Y Y , Lu K , Deng H F . Location-dependent skyline query processing in mobile databases. Proceedings of Web Information Systems and Applications Conference（WISA）, Hohhot,China, 2010
19	ChoroChronos.

符号	定义
D_i	第i个区域的数据集
D	全部数据集
u.A_i	u在第i维的属性
u_＜υ	u支配υ
u_＜sυ	u静态支配υ
dist（q,p,t）	t时刻查询点q到p的距离
SSK_locali	第i个区域的局部静态Skyline
NSSKY_locali	第i个区域的局部非静态Skyline集
SKY_locali（t）	t时刻第i个区域的局部Skyline集
SKY_global（t）	t时刻的全局Skyline集
t_in	非Skyline点成为Skyline点的时刻
t_out	Skyline点成为非Skyline点的时刻

[1]	王源,江昊,吴明,姚冬桂,张毅,羿舒文,汪海,吴静. 基于用户移动网络接入位置的高效分布式相似矩阵计算方法[J]. 电信科学, 2018, 34(5): 26-38.
[2]	李成岭,郑雨翔,洪祎祺,李雯,郭慧敏. 电网数据存储技术选型的研究[J]. 电信科学, 2018, 34(5): 183-191.
[3]	彭巍,贺晓东,陆小铭,汲传鑫. 运营商DNS海量数据分析技术优化和应用[J]. 电信科学, 2018, 34(3): 138-144.
[4]	徐海勇,黄岩. 基于PaaS技术的大数据云化平台实践[J]. 电信科学, 2018, 34(1): 148-157.
[5]	方艾,张玉忠,徐雄,金铎. 基于MapR的IPTV用户收视行为分析的方案与实践[J]. 电信科学, 2017, 33(2): 138-144.
[6]	汪保友,钱晶,袁时金. 基于Hadoop的电信大数据采集方案研究与实现[J]. 电信科学, 2017, 33(1): 135-142.
[7]	刘南海,雷蕾,王睿. 大数据时代运营商分析支撑域转型的实践与思考[J]. 电信科学, 2016, 32(8): 146-158.
[8]	谭造乐,郝志峰,蔡瑞初,肖晓军,卢宇. 基于信息增益的Hadoop瓶颈检测算法[J]. 电信科学, 2016, 32(7): 115-120.
[9]	李远宁,刘森,张诗军,陈丰,王志英. 分布式数据质量管理系统在电力企业的实践和应用[J]. 电信科学, 2016, 32(4): 169-174.
[10]	公怀予,徐劲松,王攀. 一种关联感知的大数据导入方法[J]. 电信科学, 2016, 32(3): 130-134.
[11]	谷红勋,杨珂. 基于大数据的移动用户行为分析系统与应用案例[J]. 电信科学, 2016, 32(3): 139-146.
[12]	赵会敏,雒江涛,杨军超,徐正,雷晓,罗林. 集成BP神经网络预测模型的研究与应用[J]. 电信科学, 2016, 32(2): 60-67.
[13]	王忠伟,陈叶芳,肖四友,钱江波. 一种高维大数据全k近邻查询算法[J]. 电信科学, 2015, 31(7): 52-62.
[14]	任建新,陈华辉. 一种自适应子空间相似性搜索方法[J]. 电信科学, 2015, 31(7): 63-74.
[15]	陈丽,王锐. 基于Hadoop的信令详单实时查询平台构建方法[J]. 电信科学, 2015, 31(7): 145-151.