A fast and progressive algorithm for skyline queries with totally- and partially-ordered domains

Hyungsoo Jung, Hyuck Han, Heon Y. Yeom, Sooyong Kang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

We devise a skyline algorithm that can efficiently mitigate the enormous overhead of processing millions of tuples on totally- and partially-ordered domains (henceforth, TODs and PODs). With massive datasets, existing techniques spend a significant amount of time on a dominance comparison because of both a large number of skyline points and the unprogressive method of skyline computing with PODs. (If data has high dimensionality, the situation is undoubtedly aggravated.) The progressiveness property turns out to be the key feature for solving all remaining problems. This article presents a FAST-SKY algorithm that deals successfully with these two obstacles and improves skyline query processing time strikingly, even with high-dimensional data. Progressive skyline evaluation with PODs is guaranteed by new index structures and topological sorting order. A stratification technique is adopted to index data on PODs, and we propose two new index structures: stratified R-trees (SR-trees) for low-dimensional data and stratified MinMax treaps (SM-treaps) for high-dimensional data. A fast dominance comparison is achieved by using a reporting query instead of a dominance query, and a dimensionality reduction technique. Experimental results suggest that in general cases (anti-correlated and uniform distributions) FAST-SKY is orders of magnitude faster than existing algorithms.

Original languageEnglish
Pages (from-to)429-445
Number of pages17
JournalJournal of Systems and Software
Volume83
Issue number3
DOIs
Publication statusPublished - Mar 2010
Externally publishedYes

Keywords

  • Optimality
  • Partially-ordered domain
  • Progressiveness
  • Skyline computation

Fingerprint Dive into the research topics of 'A fast and progressive algorithm for skyline queries with totally- and partially-ordered domains'. Together they form a unique fingerprint.

Cite this