TY - GEN
T1 - All-visible-k-nearest-neighbor queries
AU - Wang, Yafei
AU - Gao, Yunjun
AU - Chen, Lu
AU - Chen, Gang
AU - Li, Qing
PY - 2012/9/14
Y1 - 2012/9/14
N2 - The All-k-Nearest-Neighbor (AkNN) operation is common in many applications such as GIS and data analysis/mining. In this paper, for the first time, we study a novel variant of AkNN queries, namely All-Visible-k-Nearest-Neighbor (AVkNN) query, which takes into account the impact of obstacles on the visibility of objects. Given a data set P, a query set Q, and an obstacle set O, an AVkNN query retrieves for each point/object in Q its visible k nearest neighbors in P. We formalize the AVkNN query, and then propose efficient algorithms for AVkNN retrieval, assuming that P, Q, and O are indexed by conventional data-partitioning indexes (e.g., R-trees). Our approaches employ pruning techniques and introduce a new pruning metric called VMDIST. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of our presented pruning techniques and the performance of our proposed algorithms.
AB - The All-k-Nearest-Neighbor (AkNN) operation is common in many applications such as GIS and data analysis/mining. In this paper, for the first time, we study a novel variant of AkNN queries, namely All-Visible-k-Nearest-Neighbor (AVkNN) query, which takes into account the impact of obstacles on the visibility of objects. Given a data set P, a query set Q, and an obstacle set O, an AVkNN query retrieves for each point/object in Q its visible k nearest neighbors in P. We formalize the AVkNN query, and then propose efficient algorithms for AVkNN retrieval, assuming that P, Q, and O are indexed by conventional data-partitioning indexes (e.g., R-trees). Our approaches employ pruning techniques and introduce a new pruning metric called VMDIST. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of our presented pruning techniques and the performance of our proposed algorithms.
UR - http://www.scopus.com/inward/record.url?scp=84866022487&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-32597-7_34
DO - 10.1007/978-3-642-32597-7_34
M3 - Conference article published in proceeding or book
AN - SCOPUS:84866022487
SN - 9783642325960
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 392
EP - 407
BT - Database and Expert Systems Applications - 23rd International Conference, DEXA 2012, Proceedings
T2 - 23rd International Conference on Database and Expert Systems Applications, DEXA 2012
Y2 - 3 September 2012 through 6 September 2012
ER -