Best bin first
(Redirected from Best Bin First)
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
[edit | edit source]- 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
[edit | edit source]- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces, pp. 4-5
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |