TY - GEN
T1 - Visible reverse k-Nearest neighbor queries
AU - Gao, Yunjun
AU - Zheng, Baihua
AU - Chen, Gencai
AU - Lee, Wang Chien
AU - Lee, Ken C K
AU - Li, Qing
PY - 2009/7/8
Y1 - 2009/7/8
N2 - Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, data mining, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e.g., buildings, blindages, etc.), and their presence may affect the visibility/distance between two objects. In this paper, we introduce a novel variant of RNN queries, namely visible reverse nearest neighbor (VRNN) search, which considers the obstacle influence on the visibility of objects. Given a data set P, an obstacle set O, and a query point q, a VRNN query retrieves the points in P that have q as their nearest neighbor and are visible to q. We propose an efficient algorithm for VRNN query processing, assuming that both P and O are indexed by R-trees. Our method does not require any pre-processing, and employs half-plane property and visibility check to prune the search space.
AB - Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, data mining, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e.g., buildings, blindages, etc.), and their presence may affect the visibility/distance between two objects. In this paper, we introduce a novel variant of RNN queries, namely visible reverse nearest neighbor (VRNN) search, which considers the obstacle influence on the visibility of objects. Given a data set P, an obstacle set O, and a query point q, a VRNN query retrieves the points in P that have q as their nearest neighbor and are visible to q. We propose an efficient algorithm for VRNN query processing, assuming that both P and O are indexed by R-trees. Our method does not require any pre-processing, and employs half-plane property and visibility check to prune the search space.
UR - http://www.scopus.com/inward/record.url?scp=67649653763&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2009.201
DO - 10.1109/ICDE.2009.201
M3 - Conference article published in proceeding or book
AN - SCOPUS:67649653763
SN - 9780769535456
T3 - Proceedings - International Conference on Data Engineering
SP - 1203
EP - 1206
BT - Proceedings - 25th IEEE International Conference on Data Engineering, ICDE 2009
T2 - 25th IEEE International Conference on Data Engineering, ICDE 2009
Y2 - 29 March 2009 through 2 April 2009
ER -