A Compact-Trie-Based Structure for K-Nearest-Neighbour Searching

摘要

This paper proposes a k-nearest neighbour search method inspired by grid space partitioning and the compact-trie structure. A compact trie structure, and a k-nearest neighbour search strategy are presented. Then, a k-nearest neighbour search performance comparison is carried out against two well-known methods, using one million two-dimensional spatial points and finding up to 1000 nearest neighbours. The results of the comparison shows that the proposed compact-trie method can perform up to 300 times better when k is small, and up to 25 times better for larger k values, suggesting that the proposed method is suitable for low dimensions and location-dependent spatial queries in applications such as mobile computing.