A Technique to Identify Nearest Neighbors
- 1 October 1976
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics
- Vol. SMC-6 (10) , 678-683
- https://doi.org/10.1109/tsmc.1976.4309418
Abstract
A nonarithmetic procedure is described for discovering among a set of points in a d-dimensional space, the k neighbors nearest a given point, according to the Minkowski "max metric." It is shown that this procedure may be used to eliminate distance calculations when finding nearest neighbors according to any Minkowski p-metric. When used with a set of uniformly distributed sample points, the expected number of distance calculations n required by this technique is given by E[n] ≃ kCp,d where Cp,d is a constant determined by p and d. In the case of the Euclidean metric used in two dimensions with 1000 uniformly distributed sample points, the effective number of distance calculations required to find the nearest neighbor is approximately five.Keywords
This publication has 9 references indexed in Scilit:
- An algorithm for a selective nearest neighbor decision rule (Corresp.)IEEE Transactions on Information Theory, 1975
- An Algorithm for Finding Nearest NeighborsIEEE Transactions on Computers, 1975
- A Branch and Bound Algorithm for Computing k-Nearest NeighborsIEEE Transactions on Computers, 1975
- Finding Prototypes For Nearest Neighbor ClassifiersIEEE Transactions on Computers, 1974
- Patterns in pattern recognition: 1968-1974IEEE Transactions on Information Theory, 1974
- A generalized k-nearest neighbor ruleInformation and Control, 1970
- The condensed nearest neighbor rule (Corresp.)IEEE Transactions on Information Theory, 1968
- Nearest neighbor pattern classificationIEEE Transactions on Information Theory, 1967
- On Estimation of a Probability Density Function and ModeThe Annals of Mathematical Statistics, 1962