An Approach for Searching the Top K Nearest Areas Based on R-tree
Wenhao Lin, Yifeng Lin, Yuer Yang · 2023
The K-nearest neighbor (KNN) fundamental MBR searching is a widely used technique in navigation software. It helps locate regions, such as nearby buildings, that cannot be treated as individual entities. When searching for the top k nearest fundamental MBRs or KNN points in an unevenly distributed space, algorithms based on the R-tree prove to be the most effective ones. R-tree allows for efficient indexing and searching of multidimensional space, making it a powerful tool for spatial querying and top k nearest neighbor searching. In this paper, we compare KNN based on R-tree with linear scanning in 2D graph-based search algorithms. Experimental results demonstrate that our proposed searching algorithms based on R-tree outperform linear scanning by being approximately 95.357% faster in range querying and approximately 97.826% faster in finding the top k nearest fundamental MBRs. Furthermore, the searching algorithms based on the R-tree can be extended to find the top k nearest fundamental MBRs of q in high-dimensional spaces.