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

• 学术论文 • 上一篇    下一篇

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

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

  1. 辽宁大学信息学院, 辽宁沈阳 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   

  1. 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

摘要: 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

中图分类号: