Qskycube: Efficient skycube computation using point-based space partitioning

Jongwuk Lee, Seung Won Hwang

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


Skyline queries have gained considerable attention for multi-criteria analysis of large-scale datasets. However, the skyline queries are known to return too many results for high-dimensional data. To address this problem, a skycube is introduced to efficiently provide users with multiple skylines with different strengths. For efficient skycube construction, state-of-the-art algorithms amortized redundant computation among subspace skylines, or cuboids, either (1) in a bottom-up fashion with the principle of sharing result or (2) in a top-down fashion with the principle of sharing structure. However, we observed further room for optimization in both principles. This paper thus aims to design a more efficient skycube algorithm that shares multiple cuboids using more effective structures. Specifically, we first develop each principle by leveraging multiple parents and a skytree, representing recursive point-based space partitioning. We then design an efficient algorithm exploiting these principles. Experimental results demonstrate that our proposed algorithm is significantly faster than state-of-the-art skycube algorithms in extensive datasets.

Original languageEnglish
Pages (from-to)185-196
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number3
Publication statusPublished - 2010 Dec

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Computer Science(all)


Dive into the research topics of 'Qskycube: Efficient skycube computation using point-based space partitioning'. Together they form a unique fingerprint.

Cite this