An Algorithm for Finding Best Matches in Logarithmic Expected Time
Jerome H. Friedman, Jon Louis Bentley, Raphael A. Finkel · ACM Transactions on Mathematical Software · 1977
An algorithm and data structure are presented for searching a file containing N records, each described by k real valued keys, for the m closest matches or nearest neighbors to a given query record. The computation required to organize the file is proportional to kNlogN. The expected number of records examined in each search is independent of the file size. The expected computation to perform each search is proportional-to 1ogN. Empirical evidence suggests that except for very small files, this algorithm is considerably faster than other methods.
Cited by 2,813 works. doi:10.1145/355744.355745
Authors
References
- The Art of Computer Programming
- Multidimensional binary search trees used for associative searching
- The Art of Computer Programming
- Quad trees a data structure for retrieval on composite keys
- Constructing optimal binary decision trees is NP-complete
- Geometric complexity
- A Branch and Bound Algorithm for Computing k-Nearest Neighbors
- An Algorithm for Finding Nearest Neighbors
- Some approaches to best-match file searching
- Optimization of k nearest neighbor density estimates