Fast nearest neighbor search algorithm using the cache technique

Abstract

This paper presents a fast Nearest Neighbor Search (NNS) algorithm for geometric data sets, based on a modified k-d tree using the cache technique. First, the tree-based search process of our algorithm starts from an appropriate (cached) leaf node, not from the root node. Initial search space is restricted within small limit around the leaf node and the recursive depth-first tentative search is excluded. Therefore, the length of the node traversal path can be shortened. Second, we developed several techniques of what and how information is cached and reused. The indexing sequence of data can be good information, as well as the data itself. Generally speaking, data p(i) is an element of P are stored in consecutive order. So the indexing data pi can be similar to (i) the previous indexing data p(i-1), (ii) the same indexing data q(i) is an element of Q in another data set, and (iii) even the NNS result of the previous iteration in the Iterative Closest Point algorithm. Furthermore, we introduce a new method to apply the proposed search algorithm to even randomly sequenced data. We evaluated the algorithm with three kinds of data set (LIDAR, Kinect, and randomly generated data), and the results show that the proposed algorithm is about five times faster than the conventional approximated NNS algorithm using k-d tree.