Fast Nearest Neighbor Search using Approximate Cached k-d tree
Wonseok Choi, Se‐Young Oh · 2012
We introduce a fast Nearest Neighbor Search (NNS) algorithm using an Approximate Cached k-d tree (ACk-d tree) structure for low dimensional data sets. The search process of the standard k-d tree starts from the root node and employs a tentative back-tracking search. In contrast, the proposed method begins to search at the appropriate leaf node (cached node) and applies a depth-first nontentative search. This method improves searching speed, with tradeoff of the searching accuracy. To get a proper starting node, the proposed method is based on two properties: i) The ithquery point is likely to be close to the (i-1)thquery point, ii) The ithquery point is likely to be close to the ithmodel point. These properties are rather right, in case of practical 3D point sets which are consecutively acquired from 3D point sensors (e.g. a stereo camera, the Kinect sensor, and LIDAR). Results show that the search time of the proposed method is superior to other variants of k-d tree for practical point data sets.