Fast k-nearest neighbor classification using cluster-based trees
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 24 February 2004
Bin Zhang, Sargur N. Srihari
Citations163
SJR quartileQ1
SJR score3.91
SNIP5.99
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A cluster-based tree algorithm to accelerate k-NN classification without any presuppositions about the metric form and properties of a dissimilarity measure is proposed.
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
Computer Science
Proceedings of the IEEEGradient-based learning applied to document recognition
58,219 Citations1998Yann LeCun, Léon Bottou +2 more
This paper reviews various methods applied to handwritten character recognition and compares them on a standard handwritten digit recognition task, and Convolutional neural networks are shown to outperform all other techniques.
IEEE Transactions on Information TheoryNearest neighbor pattern classification
16,134 Citations1967Thomas M. Cover, Peter E. Hart
The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points, so it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.
Communications of the ACMMultidimensional binary search trees used for associative searching
7,467 Citations1975Jon Bentley
The multidimensional binary search tree (or k-d tree) as a data structure for storage of information to be retrieved by associative searches is developed and it is shown to be quite efficient in its storage requirements.
IEEE Transactions on Pattern Analysis and Machine IntelligenceComparing images using the Hausdorff distance
4,474 Citations1993D.P. Huttenlocher, G.A. Klanderman +1 more
Efficient algorithms for computing the Hausdorff distance between all possible relative positions of a binary image and a model are presented and it is shown that the method extends naturally to the problem of comparing a portion of a model against an image.
IEEE Transactions on ComputersA Branch and Bound Algorithm for Computing k-Nearest Neighbors
738 Citations1975Keinosuke Fukunaga, P. M. Narendra
The method of branch and bound is implemented in the present algorithm to facilitate rapid calculation of the k-nearest neighbors, by eliminating the necesssity of calculating many distances.
IEEE Transactions on Pattern Analysis and Machine IntelligencePairwise data clustering by deterministic annealing
461 Citations1997Thomas Hofmann, Joachim M. Buhmann
A deterministic annealing approach to pairwise clustering is described which shares the robustness properties of maximum entropy inference and the resulting Gibbs probability distributions are estimated by mean-field approximation.
IEEE Transactions on ComputersAn Algorithm for Finding Nearest Neighbors
388 Citations1975Jerome H. Friedman, F. Baskett +1 more
An algorithm that finds the k nearest neighbors of a point, from a sample of size N in a d-dimensional space, with an expected number of distance calculations is described, its properties examined, and the validity of the estimate verified with simulated data.
Empirical evaluation of dissimilarity measures for color and texture
362 Citations1999Jan Puzicha, Joachim M. Buhmann +2 more
It is demonstrated how the selection of a measure, based on large scale evaluation, substantially improves the quality of classification, retrieval, and unsupervised segmentation of color and texture images.
IEEE Transactions on ComputersFinding Prototypes For Nearest Neighbor Classifiers
327 Citations1974Chin-Liang Chang
An algorithm is given to find prototypes for a nearest neighbor classifier, which is to start with every sample in a training set as a prototype, and then successively merge any two nearest prototypes of the same class so long as the recognition rate is not downgraded.
IEEE Transactions on Information TheoryAn algorithm for a selective nearest neighbor decision rule (Corresp.)
326 Citations1975G. L. Ritter, H. B. Woodruff +2 more
A procedure is introduced to approximate nearest neighbor (INN) decision boundaries that produces a selective subset of the original data so that the subset is consistent, the distance between any sample and its nearest selective neighbor is less than the distance from the sample to any sample of the other class.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA simple algorithm for nearest neighbor search in high dimensions
313 Citations1997S.A. Nene, Shree K. Nayar
A simple and practical algorithm to efficiently search for the nearest neighbor within Euclidean distance /spl epsiv/ is presented and made possible to construct an inexpensive hardware search engine which can be 100 times faster than its software equivalent.
Pattern Recognition LettersAn algorithm for finding nearest neighbours in (approximately) constant average time
309 Citations1986Enrique Vidal Ruiz
A new algorithm is proposed which finds the Nearest Neighbour of a given sample in approximately constant average time complexity, independent of the data set size, thus being of general use in many present applications of Pattern Recognition.
IEEE Transactions on Pattern Analysis and Machine IntelligenceClassification with nonmetric distances: image retrieval and class representation
211 Citations2000David W. Jacobs, Daphna Weinshall +1 more
It is shown that in nonmetric spaces, boundary points are less significant for capturing the structure of a class than in Euclidean spaces, and it is suggested that atypical points may be more important in describing classes.
IEEE Transactions on Pattern Analysis and Machine IntelligenceRepresentation and recognition of handwritten digits using deformable templates
182 Citations1997Anil K. Jain, Douglas E. Zongker
The application of deformable templates to recognition of handprinted digits shows that there does exist a good low-dimensional representation space and methods to reduce the computational requirements, the primary limiting factor, are discussed.
Pattern RecognitionA note on binary template matching
125 Citations1989J. D. Tubbs
Some generalizations of binary template matching procedures which enable one to weight matches according to both statistical and spatial information are considered.
International Journal of Imaging Systems and TechnologyA multiple feature/resolution approach to handprinted digit and character recognition
121 Citations1996John T. Favata, Geetha Srikantan
The philosophy, design, and implementation of the Gradient, Structural, Concavity (GSC) recognition algorithm, which has been used successfully in several document reading applications, are outlined and applications to off‐line digit string recognition and handwritten word recognition are discussed.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Fast k Nearest Neighbor Finding Algorithm Based on the Ordered Partition
109 Citations1986Baek S. Kim, Song B. Park
It is proved that the proposed algorithm can find k nearest neighbors in a constant expected time and is distribution free, and only 4.6 distance calculations were required to find a nearest neighbor among 10 000 samples drawn from a bivariate normal distribution.
Pattern RecognitionStrategies for efficient incremental nearest neighbor search
79 Citations1990Alan Broder
It is shown that incremental search can be implemented as a sequence of invocations of a previously published non-incremental algorithm, and a new incremental search algorithm is presented which finds the next nearest neighbor more efficiently by eliminating redundant computations.
IEEE Transactions on Pattern Analysis and Machine IntelligenceFast nearest-neighbor search in dissimilarity spaces
78 Citations1993András Faragó, Tamás Linder +1 more
An exact probabilistic analysis of this family of algorithms that proves its O(1) asymptotic average complexity measured in the number of dissimilarity calculations is presented.
Discriminant Adaptive Nearest Neighbor Classification
57 Citations2003rrrevor Hastie
IEEE Transactions on Systems Man and CyberneticsAccelerated template matching using template trees grown by condensation
20 Citations1995R.L. Brown
An algorithm is presented for selecting templates from a set of training points, and organizing them into a template tree which is guaranteed to correctly identify all of the training points.
Sparse representations for image decomposition with occlusions
15 Citations1996M. Donahue, Davi Geiger +2 more
The problem of how to detect "interesting objects" appeared in a given image, I, is studied as a function approximation problem based on an over-redundant basis, and also account for occlusions, where the basis superposition principle is no longer valid.
Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004.Discovery of the tri-edge inequality with binary vector dissimilarity measures
6 Citations2004Bin Zhang, Sargur N. Srihari
The tri-edge inequality characterizing several binary distance measures is mathematically proven and experimentally verified, and the implications of TEI are discussed as well.