Constrained All-k-Nearest-Neighbor Search
Shu Long Li, Lu Chen, Qing Huo Liu, Jian Zhang · Applied Mechanics and Materials · 2012
All-k-Nearest-Neighbor (AkNN) operation is common in several applications, such as geographical information systems, data analysis, computer architecture, and so forth. However, in some real applications, users may consider AkNN search constrained to a specified region. Motivated by this, we introduce the Constrained All-k-Nearest-Neighbor (CAkNN) query that for every data in query data set A, retrieves its k NNs in data set B and located in the restricted region. In addition, we develop two efficient algorithms to answer CAkNN search, which utilize a conventional data-partitioning indexing structure (e.g., R-tree) on datasets and employ techniques includes group and plane-sweep to improve the efficiency of the search. Extensive experiments using both real and synthetic datasets demonstrate the efficiency and scalability of the proposed algorithms.