TY - GEN
T1 - Approaching the skyline in Z order
AU - Lee, Ken C.K.
AU - Zheng, Baihua
AU - Li, Huajing
AU - Lee, Wang Chien
N1 - Funding Information:
The authors would like to thank the anonymous reviewers for their constructive comments, which improved the presentation of this paper. Special thanks go to Prof. Bernhard Seeger at University of Marburg, who provided many helpful suggestions in the revision of this paper. This research is supported in part by the National Science Foundation under Grant no. IIS-0328881 and IIS-0534343.
Publisher Copyright:
Copyright 2007 VLDB Endowment, ACM.
PY - 2007
Y1 - 2007
N2 - Given a set of multidimensional data points, skyline query retrieves a set of data points that are not dominated by any other points. This query is useful for multi-preference analysis and decision making. By analyzing the skyline query, we observe a close connection between Z-order curve and skyline processing strategies and propose to use a new index structure called ZBtree, to index and store data points based on Z-order curve. We develop a suite of novel and efficient skyline algorithms, which scale very well to data dimensionality and cardinality, including (1) ZSearch, which processes skyline queries and supports progressive result delivery; (2) ZUp-date, which facilitates incremental skyline result maintenance; and (3) k-ZSearch, which answers k-dominant skyline query (a skyline variant that retrieves a representative subset of skyline results). Extensive experiments have been conducted to evaluate our proposed algorithms and compare them against the best available algorithms designed for skyline search, skyline result update, and k-dominant skyline search, respectively. The result shows that our algorithms, developed coherently based on the same ideas and concepts, soundly outperforms the state-of-the-art skyline algorithms in their specialized domains.
AB - Given a set of multidimensional data points, skyline query retrieves a set of data points that are not dominated by any other points. This query is useful for multi-preference analysis and decision making. By analyzing the skyline query, we observe a close connection between Z-order curve and skyline processing strategies and propose to use a new index structure called ZBtree, to index and store data points based on Z-order curve. We develop a suite of novel and efficient skyline algorithms, which scale very well to data dimensionality and cardinality, including (1) ZSearch, which processes skyline queries and supports progressive result delivery; (2) ZUp-date, which facilitates incremental skyline result maintenance; and (3) k-ZSearch, which answers k-dominant skyline query (a skyline variant that retrieves a representative subset of skyline results). Extensive experiments have been conducted to evaluate our proposed algorithms and compare them against the best available algorithms designed for skyline search, skyline result update, and k-dominant skyline search, respectively. The result shows that our algorithms, developed coherently based on the same ideas and concepts, soundly outperforms the state-of-the-art skyline algorithms in their specialized domains.
UR - http://www.scopus.com/inward/record.url?scp=85011072087&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85011072087&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85011072087
T3 - 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings
SP - 279
EP - 290
BT - 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings
A2 - Gehrke, Johannes
A2 - Koch, Christoph
A2 - Garofalakis, Minos
A2 - Aberer, Karl
A2 - Kanne, Carl-Christian
A2 - Neuhold, Erich J.
A2 - Ganti, Venkatesh
A2 - Klas, Wolfgang
A2 - Chan, Chee-Yong
A2 - Srivastava, Divesh
A2 - Florescu, Dana
A2 - Deshpande, Anand
PB - Association for Computing Machinery, Inc
T2 - 33rd International Conference on Very Large Data Bases, VLDB 2007
Y2 - 23 September 2007 through 27 September 2007
ER -