Skyline Query on Anti-correlated Distributions: From the Perspective of Spatial Index

Skyline query has attracted considerable attention since its introduction in databases. Algorithms for solving skyline query are proposed consecutively, and most of them ignore data distribution or assume dimensional independence, which leads to poor performance when performing such algorithms on anti-correlated distributions. To accelerate the query process, spatial index is extensively employed, and the state-of-the-art skyline algorithm for anti-correlated distributions, SOAD, is no exception as well. However, the SOAD algorithm internally uses two index structures for the step of determination and elimination respectively, which is complex to implement and imposes extra overhead for index maintenance. In this paper, we propose an efficient algorithm RSAC for anti-correlated distributions, which solely uses one index structure to implement such two steps. Experiments reveal that RSAC achieves up to 3 times performance improvement than SOAD on various datasets.