基于MapReduce的增广动态Skyline查询处理方法

doi:10.3969/j.issn.0372-2112.2018.05.006

电子学报 ›› 2018, Vol. 46 ›› Issue (5): 1062-1070.DOI: 10.3969/j.issn.0372-2112.2018.05.006

基于MapReduce的增广动态Skyline查询处理方法

丁琳琳, 崔子强, 尹显坤, 王俊陆, 宋宝燕

辽宁大学信息学院, 辽宁沈阳 110036

收稿日期:2017-02-21 修回日期:2017-09-18 出版日期:2018-05-25 发布日期:2018-05-25
通讯作者: 宋宝燕
作者简介:丁琳琳 女,1983年生于辽宁阜新,辽宁大学信息学院副教授、硕士生导师,研究方向为大数据管理、分布式数据管理、图数据管理等.E-mail:dinglinlin@lnu.edu.cn;崔子强 男,1992年出生于山东威海,辽宁大学硕士研究生,研究方向为海量数据查询.E-mail:ziqiang_c@126.com;尹显坤 男,1992年生于湖南邵阳,辽宁大学硕士研究生,研究方向为大数据管理.E-mail:jo12fjhh14@163.com;王俊陆 男,1988年生于辽宁丹东,辽宁大学中级实验师,研究方向为大数据技术、图数据管理等.E-mail:wangjunlu@lnu.edu.cn
基金资助:
国家自然科学基金（No.61472169，No.61502215，No.61472069，No.61402089，No.61572119）；辽宁省教育厅科学研究一般项目（No.L2015193）；辽宁省博士科研启动基金（No.201501127）；辽宁大学青年科研基金（No.LDQN201438）；国家重点研发计划项目（No.2016YFC0801406）

Augmented Dynamic Skyline Query Processing Method Based on MapReduce

DING Lin-lin, CUI Zi-qiang, YIN Xian-kun, WANG Jun-lu, SONG Bao-yan

School of Information, Liaoning University, Shenyang, Liaoning 110036, China

Received:2017-02-21 Revised:2017-09-18 Online:2018-05-25 Published:2018-05-25

摘要/Abstract

摘要： Skyline查询能够计算大规模的数据集中满足多个标准的最优解，被广泛应用于多目标决策等领域.动态skyline查询作为skyline查询的一种重要变体，其结果随着查询点的不同而动态改变，为用户在指定查询要求方面提供了更大的灵活性.然而，随着数据量的不断增加，动态skyline查询会产生大量的查询结果，忽略了查询点的维度方向性和数据的全局整体性，给用户的选择带来极大困难.因此，需要进一步优化动态skyline查询的结果集，提高全局整体性，过滤冗余数据.针对上述问题，提出一种基于MapReduce的增广动态skyline查询处理方法.该方法将原始数据按照维度信息进行分区，在多个节点并行计算动态skyline，优化传统动态skyline结果集，同时提供全局更优的结果供用户选择.在此基础上，针对用户给出某些维度的容忍度的情况，提出一种引入用户容忍度的增广动态skyline查询处理方法.该方法可以根据用户容忍度缩减增广动态skyline查询的原始数据集，很大程度上减少中间结果的比较次数，并且提高了结果集的准确度.大量实验证明，基于MapReduce的增广动态skyline查询处理方法具有更好的有效性、准确性和可用性.

关键词: 动态skyline查询, MapReduce, 用户容忍度, 大数据

Abstract: Skyline query can compute the optimal solution which meets the multiple standards in large-scale dataset.It has been widely applied for multi-objective decisions.Dynamic skyline query,as an important variant of skyline,its result can be dynamically changed with choosing different query points,providing more flexibility when the users make some specified needs.However,dynamic skyline query can return a large number of query results and ignore the directionality of query point and data integrality,making difficult for users to choose.It is necessary to optimize the result set of dynamic skyline,improving the whole data integrality and filtering a large number of redundant data.Focusing on these problems,we propose the augmented dynamic skyline query method based on MapReduce.The algorithm partitions the original data according to dimensional information,parallel computes dynamic skyline points in multiple nodes,optimizes the result set of the traditional dynamic skyline and at the same time provides the more global optimal results for the user to choose.In addition,when the users provide the tolerance of some dimensions,we propose the augmented dynamic skyline query with user tolerance.The algorithm reduces the original dataset according to the user tolerance and reduces the comparison times of intermediate results with improving the accuracy of the result set.The experiment results show that the augmented dynamic skyline query method based on MapReduce is efficient,accurate and scalable.

Key words: dynamic skyline query, MapReduce, user tolerance, big data

中图分类号:

TP311

丁琳琳, 崔子强, 尹显坤, 王俊陆, 宋宝燕. 基于MapReduce的增广动态Skyline查询处理方法[J]. 电子学报, 2018, 46(5): 1062-1070.

DING Lin-lin, CUI Zi-qiang, YIN Xian-kun, WANG Jun-lu, SONG Bao-yan. Augmented Dynamic Skyline Query Processing Method Based on MapReduce[J]. Acta Electronica Sinica, 2018, 46(5): 1062-1070.

参考文献

[1] Asif Zaman,Md.Anisuzzaman Siddique,Annisa,Yasuhiko Morimoto.Finding key persons on social media by using MapReduce skyline[J].International Journal of Networking and Computing,2017,7(1):86-104.
[2] Jia-Ling Koh,Chia-Ching Chen,Chih-Yu Chan,et al.MapReduce skyline query processing with partitioning and distributed dominance tests[J].Information Sciences,2017,375:114-137.
[3] 王淑艳,杨鑫,李克秋.MapReduce框架下基于超平面投影划分的Skyline计算[J].计算机研究与发展,2014,51(12):2702-2710. Wang Shuyan,Yang Xin,Li Keqiu.Skyline computing on MapReduce with hyperplane-projections-based Partition[J].Journal of Computer Research and Development,2014,51(12):2702-2710.(in Chinese)
[4] Wenlu Wang,Ji Zhang,Min-Te Sun,et al.Efficient parallel skyline evaluation using MapReduce[A].International Conference on Extending Database Technology[C].Venice,Italy:Springer Press,2017.426-437.
[5] Yoonjae Park,Jun-Ki Min,Kyuseok Shim.Efficient processing of skyline queries using MapReduce[J].IEEE Transactions on Knowledge & Data Engineering,2017,29(5):1031-1044.
[6] Yuanyuan Li,Wenyu Qu,et al.Parallel dynamic skyline query using MapReduce[A].International Conference on Cloud Computing and Big Data[C].Wuhan,China:IEEE Press,2015.95-100.
[7] Khandakar Ahmed,Nazmus S.Nafi,et al.Enhanced distributed dynamic skyline query for wireless sensor networks[J].J Sensor and Actuator Networks,2016,5(1):2.
[8] Md.Saiful Islam,Chengfei Liu,J.Wenny Rahayu,et al.Q+Tree:an efficient quad tree based data indexing for parallelizing dynamic and reverse skylines[A].International on Conference on Information and Knowledge Management[C].Indianapolis USA:ACM Press,2016.1291-1300.
[9] Karim Benouaret,Djamal Benslimane,Allel HadjAli.Selecting skyline web services for multiple users preferences[A].International Conference on Web Services[C].Hawaii USA:IEEE Press,2012.635-636.
[10] Tassadit Bouadi,Marie-Odile Cordier,et al.Computing skyline incrementally in response to online preference modification[J].Trans Large-Scale Data-and Knowledge-Centered Systems,2013,10:34-59.
[11] Yuanyuan Li,Wenyu Qu,Zhiyang Li,et al.Skyline query based on user preference with MapReduce[A].International Conference on Dependable,Autonomic and Secure Computing[C].Dalian:IEEE Press,2014.153-158.
[12] Ha Thanh Huynh Nguyen,Jinli Cao.Preference-based top-k representative skyline queries on uncertain databases[A].Pacific-Asia Conference on Knowledge Discovery and Data Mining[C].Ho Chi Minh City,Vietnam:Springer Press,2015.280-292.
[13] Yuanyuan Li,Zhiyang Li,Mianxiong Dong,et al.Efficient subspace skyline query based on user preference using MapReduce[J].Ad Hoc Networks,2015,35(C):105-115.
[14] Markus Endres,Timotheus Preisinger:Beyond skylines:explicit preferences[A].International Conference on Database Systems for Advanced Applications[C].Suzhou China:Springer Press,2017.327-342.
[15] Arun K.Pujari,Venkateswara Rao Kagita,et al.Efficient computation for probabilistic skyline over uncertain preferences[J].Information Sciences,2015,324(C):146-162.
[16] Qing Zhang,Pengjie Ye,Xuemin Lin,et al.Skyline probability over uncertain preferences[A].International Conference on Extending Database Technology[C].Genoa,Italy:ACM Press,2013.395-405.
[17] Stephan Børzsønyi,Donald Kossmann,Konrad Stocker:The skyline operator[A].International Conference on Data Engineering[C].Heidelberg,Germany:IEEE Press,2001.421-430.
[18] ChoroChronos[DB/OL].http://www.chorochronos.org/.

基于MapReduce的增广动态Skyline查询处理方法

Augmented Dynamic Skyline Query Processing Method Based on MapReduce

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	侯秀聪, 赖晓平, 曹九稳. 正则化超限学习机的最大分划广义交替方向乘子法[J]. 电子学报, 2021, 49(4): 625-630.
[2]	杨洋. 改进帕累托算法求解超大规模多选择背包问题[J]. 电子学报, 2020, 48(6): 1205-1212.
[3]	陆佳炜, 吴涵, 陈烘, 张元鸣, 梁倩卉, 肖刚. 一种基于动态拓扑的流计算性能优化方法及其在Storm中的实现[J]. 电子学报, 2020, 48(5): 878-890.
[4]	徐超, 陈勇, 葛红美, 何炎祥. 基于大数据的审计技术研究[J]. 电子学报, 2020, 48(5): 1003-1017.
[5]	江小玉, 李贵洋, 周悦, 胡金平, 李慧. 基于负载均衡的纠删码修复流水线[J]. 电子学报, 2020, 48(5): 930-936.
[6]	张鹏, 叶剑, 张鹏. 基于概念漂移检测的大数据交易过程模型优化方法[J]. 电子学报, 2019, 47(7): 1465-1474.
[7]	魏波, 吴瑞峰, 张文生, 吕敬钦, 王莹莹, 夏学文. 具有双重稀疏机制的在线学习算法[J]. 电子学报, 2019, 47(10): 2202-2210.
[8]	金宏桥, 董一鸿, 陈华辉, 钱江波. 分布式环境下基于马尔科夫链的图流三角近似计算[J]. 电子学报, 2018, 46(9): 2139-2148.
[9]	郭艺, 叶剑, 张鹏. 基于偏差约减的大数据交易模型分析与修复方法[J]. 电子学报, 2018, 46(7): 1754-1761.
[10]	尹鑫, 田有亮, 王海龙. 面向大数据定价的委托拍卖方案[J]. 电子学报, 2018, 46(5): 1113-1120.
[11]	米允龙, 李金海, 刘文奇, 林晶. MapReduce框架下的粒概念认知学习系统研究[J]. 电子学报, 2018, 46(2): 289-297.
[12]	朱皖宁, 刘志昊. 基于量子计算的用户识别算法[J]. 电子学报, 2018, 46(1): 24-30.
[13]	任正伟, 孙小雁, 王丽娜, 王骞, 徐明迪, 张茂胜. 基于简单随机抽样的大数据可信性验证方法[J]. 电子学报, 2017, 45(10): 2484-2490.
[14]	梁俊杰, 李凤华, 刘琼妮, 尹利. MapReduce框架下的优化高维索引与KNN查询[J]. 电子学报, 2016, 44(8): 1873-1880.
[15]	赵卓峰, 丁维龙, 张帅. 海量车牌识别数据集上基于时空划分的旅行时间计算方法[J]. 电子学报, 2016, 44(5): 1227-1233.