Best bin first is a search algorithm

Search algorithm

In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...

 that is designed to efficiently find an approximate solution to the nearest neighbor search

Nearest neighbor search

Nearest neighbor search , also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest points in metric spaces. The problem is: given a set S of points in a metric space M and a query point q ∈ M, find the closest point in S to q...

 problem in very-high-dimensional spaces. The algorithm is based on a variant of the kd-tree

Kd-tree

In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...

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.

Difference from kd tree

• Backtracking is according to a priority queue based on closeness.
• Search a fixed number of nearest candidates and stop.
• A speedup of two orders of magnitude is typical.