Home // International Journal On Advances in Software, volume 8, numbers 3 and 4, 2015 // View article

Looking for the Best, but not too Many of Them: Multi-Level and Top-k Skylines

Authors:
Timotheus Preisinger
Markus Endres

Keywords: Skyline; Preferences; Multi-level; Top-k; Lattice

Abstract:
The problem of Skyline computation has attracted considerable research attention in the last decade. A Skyline query selects those tuples from a dataset that are optimal with respect to a set of designated preference attributes. However, the number of Skyline answers may be smaller than required by the user, who needs at least k. Given a dataset, a top-k Skyline query returns the k most interesting elements of the Skyline query based on some kind of user-defined preference. That said, in some cases, not only the Pareto frontier is of interest, but also the stratum behind the Skyline to get exactly the top-k objects from a partially ordered set stratified into subsets of non-dominated tuples. In this paper we present the concept of multi-level Skylines for the computation of different strata and we discuss top-k Skyline queries in detail. Our algorithms rely on the lattice structure constructed by a Skyline query over low-cardinality domains. In addition we present external versions of our algorithms such that it is not necessary to store the complete lattice in main memory. We demonstrate through extensive experimentation on synthetic and real datasets that our algorithms can result in a significant performance advantage over existing techniques.

Pages: 467 to 480

Copyright: Copyright (c) to authors, 2015. Used with permission.

Publication date: December 30, 2015

Published in: journal

ISSN: 1942-2628