Top-k Skyline Result Optimization Algorithm in MapReduce

摘要

Skyline is widely used in multi-objective decision-making, data visualization and other fields. With the rapid increasing of data volume, skyline of big data has also attracted more and more attention. However, skyline of big data has its own shortcomings. When the dimension increases, skyline results will be numerous, and we would like to select k points from the result sets. In this paper, we propose the top-k skyline of big data. It is a Top-k Skyline Method in MapReduce, called MR-DMKS. Firstly, we convert the multidimensional data to a single value to determine the dominance relationship of two data points. Secondly, we calculate the score by using the converted values. Thirdly, sort the data points more efficiently and accurately according to the scores using a window queue. Finally, we choose k data objects having the strongest dominating capacity. A large number of experiments show that our method is effective, and has good flexibility and scalability on real data sets as well as synthetic data sets.