Approximate Best Bin First k-d Tree All Nearest Neighbor Search with Incremental Updates
Jan Kybic, Ivan Vnu · 2010
We describe an approximate algorithm to find all nearest neighbors (NN) for a set of points in moderate to high-dimensional spaces. Al-though the method is generally applicable, it is tailored to our main application, which is a NN-based entropy estimation for an image similarity criterion for image registration. Our algorithm is unique for having simultaneously the following features: (i) It is usable for millions of data points in several tens of dimensions. (ii) It can deal with multiple points. (iii) It offers a speedup of the all-NN search task with respect to repeating a NN search for each query point. (iv) It allows exact as well as approximate search when reduced search time is needed. (v) The search tree can be updated incrementally when the change of values of the data points is small. The method is based on creating a balanced k-d tree, which is then searched using the best-bin-first strategy. The tree nodes contain both tight and loose bounding boxes. The method is presented using NN defined in an ` ∞ norm but can be applied to the `2 norm, too. We present a number of experiments demonstrating the behavior of our algorithm. We compare the presented method with a state-of-the-art approximate nearest neighbor search library ANN and we observe that the new method is superior for exact search and high number of points as well as for approximate search in small to mod-erate dimensions or when a fast approximation is needed. 1 1