Dynamic skyline computation on massive data

摘要

In many applications, dynamic skyline query is an important operation to find the interesting tuples in a potentially huge data space. Given the query point, dynamic skyline query returns tuples which are not dynamically dominated by other tuples. It is found that the existing algorithms cannot process dynamic skyline query on massive data efficiently. This paper proposes a novel dynamic-sorted-list-based DDS algorithm to efficiently compute dynamic skyline results on massive data. Given the query point, the dynamic sorted list of each attribute is not materialized but generated dynamically by the sorted list of the attribute. DDS retrieves the tuples in the involved dynamic sorted lists in the round-robin fashion until the early termination condition is satisfied, and computes the dynamic skyline results by retrieving the candidates. The pruning operation is devised to reduce the number of the retrieved candidates. The extensive experimental results, conducted on synthetic and real-life data sets, show that DDS outperforms the existing algorithms significantly.