Efficient Skyline Computation in High-Dimensionality Domains

Rui Liu (1) , Dominique H. Li (2, 1, 3)

1 UT - Université de Tours
2 LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours
3 BDTLN - Bases de données et traitement des langues naturelles

We present a dimension indexing based algorithm for skyline computation. We first show that the dominance tests required to determine a skyline tuple can be sufficiently bounded to a subset of the current skyline, and then propose the algorithm SDI, of which the time complexity is better than the best known algorithm in high-dimensionality domains with reasonably low cardinality. Our performance evaluation on synthetic and real datasets shows that SDI outperforms the state-of-the-art skyline algorithm in both low-dimensionality and high-dimensionality domains.

Domaines: Informatique [cs]; Base de données [cs.DB]

Rui Liu, Dominique H. Li. Efficient Skyline Computation in High-Dimensionality Domains. EDBT 2020, Mar 2020, Copenhagen, Denmark. ⟨10.5441/002/edbt.2020.57⟩. ⟨hal-02530320⟩