SkyMap: A Trie-Based Index Structure for High-Performance Skyline Query Processing

摘要: Skyline queries have become commonplace in many applications. The main problem is to efficiently find the set of Pareto-optimal choices from a large amount database items. Several algorithms and indexing techniques been proposed recently, but until now no technique was able address all problems for skyline realistic applications: fast access, superior scalability even higher dimensions, low costs maintenance face data updates. In this paper we design evaluate trie-based that solves major efficiency bottlenecks queries. It scales gracefully high dimensional queries, largely independent underlying distributions, allows efficient Our experiments on real synthetic datasets show performance increase up two orders magnitude compared previous techniques.