Abstract
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 logN. Empirical evidence suggests that except for very small files, this algorithm is considerably faster than other methods.
Keywords
LogarithmComputationComputer scienceAlgorithmMathematicsCombinatorics
Related Publications
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs
We present a new approach for the approximate K-nearest neighbor search based on navigable small world graphs with controllable hierarchy (Hierarchical NSW, HNSW). The proposed ...
The K-D-B-tree
The problem of retrieving multikey records via range queries from a large, dynamic index is considered. By large it is meant that most of the index must be stored on secondary m...
An Algorithm for Finding Best Matches in Logarithmic Expected Time
article Free Access Share on An Algorithm for Finding Best Matches in Logarithmic Expected Time Authors: Jerome H. Friedman Stanford Linear Accelerator Center, Stanford Universi...
Organization and maintenance of large ordered indices
Organization and maintenance of an index for a dynamic random access file is considered. It is assumed that the index must be kept on some pseudo random access backup store like...
The Grid file: A data structure designed to support proximity queries on spatial objects
Abstract : This document describes a technique for storing large sets of spatial objects so that proximity queries are handled efficiently as part of the accessing mechanism. Th...
Publication Info
- Year
- 1976
- Type
- article
- Citations
- 9
- Access
- Closed
External Links
Citation Metrics
9
OpenAlex
Cite This
Jerome H. Friedman,
Jon Bentley,
Raphael A. Finkel
(1976).
An Algroithm for Finding Best Matches in Logarithmic Expected Time.
.