DFTS:面向大数据集的Top-k Skyline查询算法  

DFTS:A Top-k Skyline Query for Large Datasets

作　　者：魏亮 林子雨[1] 赖永炫[2,3] WEI Liang;LIN Zi-yu;LAI Yong-xuan(School of Information Science and Engineering,Xiamen University,Xiamen,Fujian 361005,China;School of Software,Xiamen University,Xiamen,Fujian 361005,China;Shenzhen Research Institute,Xiamen University,Shenzhen,Guangdong 518000,China)

机构地区：[1]厦门大学信息科学与技术学院,福建厦门361005 [2]厦门大学软件学院,福建厦门361005 [3]厦门大学深圳研究院,广东深圳518000

出　　处：《计算机科学》2019年第5期150-156,共7页Computer Science

基　　金：国家自然科学基金(61672441);深圳市基础研究计划(JCYJ20170818141325209)资助

摘　　要：Top-k Skyline查询结合了Top-k与Skyline的特性,可以在数据集中找到最好的点。但是,现有的算法在大数据环境下具有较高的时间开销。文中提出一种新的算法DFTS,其可以高效地在大数据集中进行Top-k Skyline查询。DFTS包括3个步骤:首先,利用度值评价函数对数据集进行排序,快速过滤掉大量的点,仅保留足够少的候选集;然后,对候选集进行Skyline查询计算,进一步排除掉Skyline集合外的点;最后,筛选出Top-k的数据点作为最终结果。通过这种方式,DFTS有效减少了算法的运行时间。从理论上证明了DFTS查询的最终结果符合Top-k Skyline查询的要求。基于大数据集的大量实验表明,DFTS具有比现有算法更好的性能。Top-k Skyline query combines the features of Top-k query and Skyline,which can find the best object in the datasets.However,the available methods can not fit to large datasets well.An efficient Top-k Skyline query method called DFTS was proposed,which can perform well for large datasets.DFTS involves three steps.Firstly,the degreescore function is used to rank the dataset,and a large quantity of objects with low ranking will be filtered out.Secondly,DFTS makes a Skyline query upon the candidates and generates a Skyline subset.Finally,top-k objects with high ran-king will be selected from the Skyline subset as the final result.Through these steps,DFTS can significantly reduce the time cost.It is proved that the results of DFTS satisfy the demand of Top-k Skyline query.Extensive experimental results show that DFTS can achieve much better performance for large datasets than state-of-the-art methods.

关 键 词：SKYLINE TOP-K APACHE SPARK 

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