| 释义 |
- Differences from kd tree
- References
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 order to increasing 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. ^{{cite conference | last1 = Beis | first1=J. | last2 = Lowe | first2 = D. G. | year = 1997 | title = Shape indexing using approximate nearest-neighbour search in high-dimensional spaces | citeseerx = 10.1.1.23.9493 | conference = Conference on Computer Vision and Pattern Recognition | location = Puerto Rico | pages = 1000–1006 }}
2. ^Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces, pp. 4-5
{{algorithm-stub}} 1 : Search algorithms |