On Processing Reverse k-skyband and Ranked Reverse Skyline Queries
In this paper, for the first time, we identify and solve the problem of efficient reverse k-skyband (RkSB) query processing. Given a set P of multi-dimensional points and a query point q, an RkSB query returns all the points in P whose dynamic k-skyband contains q. We formalize RkSB retrieval, and then propose five algorithms for computing the RkSB of an arbitrary query point efficiently. Our methods utilize a conventional data-partitioning index (e.g., R-tree) on the dataset, and employ pre-computation, reuse and pruning techniques to boost the query efficiency. In addition, we extend our solutions to tackle an interesting variant of reverse skyline queries, namely, ranked reverse skyline (RRS) query where, given a data set P, a parameter K, and a preference function f, the goal is to find the K reverse skyline points that have the minimal score according to the user-specified function f. Extensive experiments using both real and synthetic data sets demonstrate the effectiveness of our proposed pruning heuristics and the performance of our proposed algorithms under a variety of experimental settings.
skyline, reverse k-skyband, ranked reverse skyline, query processing, algorithm
Computer Sciences | Databases and Information Systems | Theory and Algorithms
Data Management and Analytics
GAO, Yunjun; LIU, Qing; ZHENG, Baihua; LI, Mou; CHEN, Gang; and LI, Qing.
On Processing Reverse k-skyband and Ranked Reverse Skyline Queries. (2015). Information Sciences. 293, 11-34. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/2467