Best bin first: Difference between revisions
Content deleted Content added
Kiwiderpia (talk | contribs) →Differences from kd tree: Fixed grammar Tags: canned edit summary Mobile edit Mobile app edit Android app edit |
Olexa Riznyk (talk | contribs) Adding priority queue wikilink |
||
| Line 3: | Line 3: | ||
== Differences from kd tree == |
== 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.<ref>[http://www.cs.ubc.ca/~lowe/papers/cvpr97.pdf Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces, pp. 4-5]</ref> |
* 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]].<ref>[http://www.cs.ubc.ca/~lowe/papers/cvpr97.pdf Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces, pp. 4-5]</ref> |
||
* Search a fixed number of nearest candidates and stop. |
* Search a fixed number of nearest candidates and stop. |
||
* A speedup of two orders of magnitude is typical. |
* A speedup of two orders of magnitude is typical. |
||
Latest revision as of 18:51, 22 January 2023
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]- 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]- ^ 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. |