Advertisement
Published in:
2015 | OriginalPaper | Chapter
Scalagon: An Efficient Skyline Algorithm for All Seasons
Authors : Markus Endres, Patrick Roocks, Werner Kießling
Published in: Database Systems for Advanced Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Skyline queries are well-known in the database community and there are many algorithms for the computation of the Pareto frontier. The most prominent algorithms are based on a block-nested-loop style tuple-to-tuple comparison (BNL). Another approach exploits the lattice structure induced by a Skyline query over low-cardinality domains. In this paper, we present
Scalagon
, an algorithm which combines the ideas of the lattice approach and a BNL-style algorithm to evaluate Skylines on arbitrary domains. Since multicore processors are going mainstream, we also present a parallel version of Scalagon. We demonstrate through extensive experimentation on synthetic and real datasets that our algorithm can result in a significant performance advantage over existing techniques.