DFTS：面向大数据集的Top-k Skyline查询算法
魏亮1+, 林子雨1,赖永炫2,3
1.厦门大学 信息科学与技术学院, 福建省 厦门市 361005
2.厦门大学 软件学院，福建省 厦门市 361005
3.厦门大学深圳研究院，广东省深圳市518000
DFTS：An Efficient Top-k Skyline Query for Large Datasets
Liang Wei1+, Ziyu Lin1, Yongxuan Lai2,3
1.Department of Computer Science, Xiamen University, Xiamen 361005, China
2. School of Software,Xiamen University, Xiamen 361005, China
3. Shenzhen Research Institute, Xiamen University, Shenzhen 518000, China
+ Corresponding author: E-mail: waylion@stu.xmu.edu.cn
WEI Liang, LIN Ziyu, LAI Yongxuan. DFTS：An Efficient Top-k Skyline Query for Large Datasets. Journal of Frontiers of Computer Science and Technology, 2018,.
Abstract:Top-k Skyline query combines the features of Top-k query and Skyline query, which can find those best objects in the datasets. However, the available methods can not fit to large datasets well. Here an efficient Top-k Skyline query method called DFTS is 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 ranking will be selected from the Skyline subset as the final result. Through these steps, DFTS can significantly reduce the time cost. Here it is proved that the result of DFTS satisfies the demand of Top-k Skyline query. Extensive experimental results show that DFTS can achieve much better performance for large datasets than those state-of-the-art methods.
Key words:Skyline; Top-k; Apache Spark
摘 要:Top-k Skyline查询结合了Top-k与Skyline的特性，可以在数据集中找到最好的那些点。但是，现有的算法在大数据环境下具有较高的时间开销。本文提出一种新的算法DFTS，可以高效地在大数据集中进行Top-k Skyline查询。DFTS包括三个步骤，首先，利用“度值”评价函数对数据集进行排序，快速过滤掉大量的点，仅保留足够小的候选集；然后，对候选集进行Skyline查询计算，进一步排除掉Skyline集合外的点；最后，筛选出Top-k的数据点作为最终结果。通过这种方式，DFTS有效减小了算法运行时间开销。本文在理论上证明了，查询的最终结果符合Top-k Skyline查询的要求。基于大数据集的大量实验表明，DFTS相比于现有的算法具有更好的性能。
关键词：Skyline；Top-k；Apache Spark
（上图 魏亮同学在NDBC2018会议分组报告中介绍自己的论文）
（上图 魏亮同学在NDBC2018会议分组报告中介绍自己的论文）
