海量不完整数据上基于维度组合的Skyline查询  

Skyline Query of Massive Incomplete Data Based on Combinational Dimensions

作　　者：王妍[1,2] 银彪 刘赓浩[1] 宋宝燕[1] 王俊陆[1] 

机构地区：[1]辽宁大学信息学院,沈阳110036 [2]东北大学信息与工程学院,沈阳110819

出　　处：《计算机科学与探索》2016年第4期495-503,共9页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金Nos.61472072;61472169;61300233;国家重点基础研究发展计划(973计划)No.2014CB360509;国家科技支撑计划No.2012BAF13B08;辽宁省科学事业公益研究基金项目No.2015003003;辽宁大学青年科研基金No.LDQN201508~~

摘　　要：随着互联网、物联网等信息技术的快速发展,多维数据日益增多,这些海量数据中往往伴随着大量的不完整数据,如何从海量不完整数据中高效地获取用户所需的近似的结果集是一个亟需解决的问题。针对海量高维的不完整数据集,提出了一种基于维度组合的Skyline查询算法,通过构建Rank List数据结构提高查询效率,并减少不完整数据对查询结果的影响;利用维度的不同组合,划分出查询子空间,并渐进地查询出每个子空间的最优先点,从而获得海量不完整数据集上均匀分布的Skyline点。实验结果表明,该算法与Iskyline算法相比,平均查询效率提高了85%,并且在数据量大、维度高时,较普通方法查询效率更高。With the rapid development of Internet, Internet of things and other information technology, and multidimensional data increasing, these massive data are often accompanied by a large number of incomplete data. So how to efficiently get the approximate result sets required by users from the massive incomplete data is an urgent problem to solve. This paper proposes a Skyline query algorithm for the massive high-dimensional incomplete data sets based on combination of dimensions. The algorithm constitutes Rank List data structure to improve query efficiency and reduce the impact of incomplete data for query results, divides query subspaces by combining different dimensions, and incrementally checks out the highest priority point in the subspace, that is Skyline points uniformly distributed in the incomplete data set. The experimental results show that, compared with the Iskyline algorithm, the query efficiency of the proposed algorithm increases by 85% on average. And when the data are huge amount and high dimension, the algorithm shows higher query efficiency than the ordinary methods.

关 键 词：海量不完整数据 维度组合 SKYLINE 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]