TY - GEN
T1 - On efficient reverse k-skyband query processing
AU - Liu, Qing
AU - Gao, Yunjun
AU - Chen, Gang
AU - Li, Qing
AU - Jiang, Tao
PY - 2012/5/11
Y1 - 2012/5/11
N2 - This paper, for the first time, addresses 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 the RkSB query, and then propose three 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, as well as employ pre-computation and pruning techniques to improve the query performance. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of our proposed pruning heuristics and the performance of our proposed algorithms.
AB - This paper, for the first time, addresses 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 the RkSB query, and then propose three 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, as well as employ pre-computation and pruning techniques to improve the query performance. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of our proposed pruning heuristics and the performance of our proposed algorithms.
UR - http://www.scopus.com/inward/record.url?scp=84860668004&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-29038-1_39
DO - 10.1007/978-3-642-29038-1_39
M3 - Conference article published in proceeding or book
AN - SCOPUS:84860668004
SN - 9783642290374
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 544
EP - 559
BT - Database Systems for Advanced Applications - 17th International Conference, DASFAA 2012, Proceedings
T2 - 17th International Conference on Database Systems for Advanced Applications, DASFAA 2012
Y2 - 15 April 2012 through 18 April 2012
ER -