Z-SKY: an efficient skyline query processing framework based on Z-order

• Published in: The VLDB journal 2010-06, Vol.19 (3), p.333-362
• Main Authors: Lee, Ken C. K., Lee, Wang-Chien, Zheng, Baihua, Li, Huajing, Tian, Yuan
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Computer Science; Computer science; control theory; systems; Database Management; Exact sciences and technology; Information systems. Data bases; Memory organisation. Data processing; Regular Paper; Software; Theoretical computing
• ISSN: 1066-8888; 0949-877X
• DOI: 10.1007/s00778-009-0166-x

Given a set of data points in a multidimensional space, a skyline query retrieves those data points that are not dominated by any other point in the same dataset. Observing that the properties of Z-order space filling curves (or Z-order curves) perfectly match with the dominance relationships among data points in a geometrical data space, we, in this paper, develop and present a novel and efficient processing framework to evaluate skyline queries and their variants, and to support skyline result updates based on Z-order curves. This framework consists of ZBtree , i.e., an index structure to organize a source dataset and skyline candidates, and a suite of algorithms, namely, (1) ZSearch , which processes skyline queries, (2) ZInsert , ZDelete and ZUpdate , which incrementally maintain skyline results in presence of source dataset updates, (3) ZBand , which answers skyband queries, (4) ZRank , which returns top-ranked skyline points, (5) k-ZSearch , which evaluates k -dominant skyline queries, and (6) ZSubspace , which supports skyline queries on a subset of dimensions. While derived upon coherent ideas and concepts, our approaches are shown to outperform the state-of-the-art algorithms that are specialized to address particular skyline problems, especially when a large number of skyline points are resulted, via comprehensive experiments.