Best_bin_first

Best bin first

Best bin first

Add article description

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

  • Bins are looked in increasing order of distance from the query point. The distance to a bin is defined as a minimal distance to any point of its boundary. This is implemented with priority queue.[2]
  • Search a fixed number of nearest candidates and stop.
  • A speedup of two orders of magnitude is typical.

References

  1. [1]
    Beis, J.; Lowe, D. G. (1997). Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. Conference on Computer Vision and Pattern Recognition. Puerto Rico. pp. 1000–1006. CiteSeerX 10.1.1.23.9493.
  2. [2]
    Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces, pp. 4-5


Stub icon

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.
Share this article:

This article uses material from the Wikipedia article Best_bin_first, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.