Best bin first explained

Best bin first is a search algorithm that is designed to efficiently find an approximate solution to the nearest neighbor search problem in very-high-dimensional spaces. The algorithm is based on a variant of the kd-tree search algorithm which makes indexing higher-dimensional spaces possible. Best bin first is an approximate algorithm which returns the nearest neighbor for a large fraction of queries and a very close neighbor otherwise.[1]

Differences from kd tree

Notes and References

  1. Beis . J. . Lowe . D. G. . 1997 . Shape indexing using approximate nearest-neighbour search in high-dimensional spaces . 10.1.1.23.9493 . Conference on Computer Vision and Pattern Recognition . Puerto Rico . 1000–1006 .
  2. http://www.cs.ubc.ca/~lowe/papers/cvpr97.pdf Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces, pp. 4-5