Fast k-nearest neighbor classification using cluster-based trees
- 19 February 2004
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Ieee Transactions On Pattern Analysis and Machine Intelligence
- Vol. 26 (4), 525-528
- https://doi.org/10.1109/tpami.2004.1265868
Abstract
Most fast k-nearest neighbor (k-NN) algorithms exploit metric properties of distance measures for reducing computation cost and a few can work effectively on both metric and nonmetric measures. We propose a cluster-based tree algorithm to accelerate k-NN classification without any presuppositions about the metric form and properties of a dissimilarity measure. A mechanism of early decision making and minimal side-operations for choosing searching paths largely contribute to the efficiency of the algorithm. The algorithm is evaluated through extensive experiments over standard NIST and MNIST databases.Keywords
This publication has 22 references indexed in Scilit:
- Classification with nonmetric distances: image retrieval and class representationIeee Transactions On Pattern Analysis and Machine Intelligence, 2000
- Empirical evaluation of dissimilarity measures for color and texturePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- A multiple feature/resolution approach to handprinted digit and character recognitionInternational Journal of Imaging Systems and Technology, 1996
- Fast nearest-neighbor search in dissimilarity spacesIeee Transactions On Pattern Analysis and Machine Intelligence, 1993
- Strategies for efficient incremental nearest neighbor searchPattern Recognition, 1990
- An algorithm for a selective nearest neighbor decision rule (Corresp.)IEEE Transactions on Information Theory, 1975
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Finding Prototypes For Nearest Neighbor ClassifiersIEEE Transactions on Computers, 1974
- The condensed nearest neighbor rule (Corresp.)IEEE Transactions on Information Theory, 1968
- Nearest neighbor pattern classificationIEEE Transactions on Information Theory, 1967