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 treeEdit
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.
ReferencesEdit
^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. CiteSeerX10.1.1.23.9493.
^Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces, pp. 4-5
best, first, search, algorithm, that, designed, efficiently, find, approximate, solution, nearest, neighbor, search, problem, very, high, dimensional, spaces, algorithm, based, variant, tree, search, algorithm, which, makes, indexing, higher, dimensional, spac. 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 EditBins 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 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 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 vte Retrieved from https en wikipedia org w index php title Best bin first amp oldid 1135116380, wikipedia, wiki, book, books, library,
