A nearest neighbor search method suitable for low dimensions and location-dependent spatial queries in mobile computing

Abstract

This thesis proposes a k-nearest-neighbor search method inspired by the grid space partitioning and the compact trie tree structure. A detailed implementation based on the Best-First-Nearest-Neighbor-Search scheme is presented and illustrated with sample data. Then k-nearest-neighbor search performance comparison is carried out among the proposed compact-trie-based method, the brute-force method, and the k-d tree based method, with one million two-dimensional spatial points and k up to 1000. The result of the comparison shows that the proposed method can perform up to 300 times better than the other two methods when k is small, suggesting that the proposed method might be suitable for low dimensions and location-dependent spatial queries in mobile computing.