Subset Approach to Efficient Skyline Computation - Laboratoire d'Informatique Fondamentale et Appliquée de Tours Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

Subset Approach to Efficient Skyline Computation

Résumé

Skyline query processing is essential to the database community. Many algorithms have been designed to perform efficient skyline computation, which can be generally categorized into sorting-based and partitioning-based by considering the different mechanisms to reduce the dominance tests. Sorting-based skyline algorithms first sort all points with respect to a monotone score function, for instance the sum of all values of a point, then the dominance tests can be bounded by the score function; partitioning-based algorithms create partitions from the dataset so that the dominance tests can be limited in partitions. On the other hand, the incomparability between points has been considered as an important property, that is, if two points are incomparable, then any dominance test between them is unnecessary. In fact, the state-of-the-art skyline algorithms effectively reduce the dominance tests by taking the incomparability into account. In this paper, we present a subset-based approach that allows to integrate subspace-based incomparability to existing sorting-based skyline algorithms and can therefore significantly reduce the total number of dominance tests in large multidimensional datasets. Our theoretical and experimental studies show that the proposed subset approach boosts existing sorting-based skyline algorithms and makes them comparable to the state-ofthe-art algorithms and even faster with uniform independent data.
Fichier principal
Vignette du fichier
edbt23subset.pdf (653.23 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03961833 , version 1 (29-01-2023)

Identifiants

Citer

Dominique H. Li. Subset Approach to Efficient Skyline Computation. The 26th International Conference on Extending Database Technology (EDBT), Mar 2023, Ioannina, Greece. ⟨10.48786/edbt.2023.31⟩. ⟨hal-03961833⟩
40 Consultations
25 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More