article

An improved branch and bound algorithm for computing k-nearest neighbors

Authors:

Behrooz Kamgar-Parsi,

Laveen N KanalAuthors Info & Claims

Pattern Recognition Letters, Volume 3, Issue 1

Pages 7 - 12

https://doi.org/10.1016/0167-8655(85)90036-4

Published: 01 January 1985 Publication History

Abstract

In 1975 Fukunaga and Narendra proposed an efficient branch and bound algorithm for computing k-nearest neighbors. Their algorithm, after a hierarchical decomposition of the design set into disjoint subsets, employs two rules in order to eliminate the necessity of calculating many distances. This correspondence discusses the applicability of two additional rules for a further reduction of the number of distance computations. Experimental results using samples from bivariate Gaussian and uniform distributions suggest that the number of distance computations required by the modified is typicaly one fourth of that of the Fukunaga-Narendra algorithm.

Reference

[1]

Funkunaga, K and Narendra, P.M, A branch and bound algorithm for computing k-nearest neighbors. IEEE Trans. Comput. v24. 750-753.

Digital Library

Google Scholar

Cited By

View all

Zhao ZMa ZYan L(2021)An Efficient Classification of Fuzzy XML Documents Based on Kernel ELMInformation Systems Frontiers10.1007/s10796-019-09973-323:3(515-530)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10796-019-09973-3
Ban TKadobayashi Y(2007)New prune rules for similarity searchProceedings of The Eleventh IASTED International Conference on Artificial Intelligence and Soft Computing10.5555/1659652.1659675(120-126)Online publication date: 9-Aug-2007
https://dl.acm.org/doi/10.5555/1659652.1659675
Goswami PDas SNandy S(2007)Chromatic distribution of k-nearest neighbors of a line segment in a planar colored point setInformation Processing Letters10.1016/j.ipl.2006.12.010102:4(163-168)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.1016/j.ipl.2006.12.010
Show More Cited By

Recommendations

A Branch and Bound Algorithm for Computing k-Nearest Neighbors

Computation of the k-nearest neighbors generally requires a large number of expensive distance computations. The method of branch and bound is implemented in the present algorithm to facilitate rapid calculation of the k-nearest neighbors, by ...
PCA-based branch and bound search algorithms for computing K nearest neighbors

In this paper, the efficiency of branch and bound search algorithms for the computation of K nearest neighbors is studied. The most important aspects that influence the efficiency of the search algorithm are: (1) the decomposition method, (2) the ...
Extending LAESA Fast Nearest Neighbour Algorithm to Find the k Nearest Neighbours
Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition

Many pattern recognition tasks make use of the k nearest neighbour (k-NN) technique. In this paper we are interested on fast k- NN search algorithms that can work in any metric space i.e. they are not restricted to Euclidean-like distance functions. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Pattern Recognition Letters Volume 3, Issue 1

January, 1985

73 pages

ISSN:0167-8655

Issue’s Table of Contents

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 January 1985

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhao ZMa ZYan L(2021)An Efficient Classification of Fuzzy XML Documents Based on Kernel ELMInformation Systems Frontiers10.1007/s10796-019-09973-323:3(515-530)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10796-019-09973-3
Ban TKadobayashi Y(2007)New prune rules for similarity searchProceedings of The Eleventh IASTED International Conference on Artificial Intelligence and Soft Computing10.5555/1659652.1659675(120-126)Online publication date: 9-Aug-2007
https://dl.acm.org/doi/10.5555/1659652.1659675
Goswami PDas SNandy S(2007)Chromatic distribution of k-nearest neighbors of a line segment in a planar colored point setInformation Processing Letters10.1016/j.ipl.2006.12.010102:4(163-168)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.1016/j.ipl.2006.12.010
Gómez-Ballester EMicó LOncina J(2006)Some approaches to improve tree-based nearest neighbour search algorithmsPattern Recognition10.1016/j.patcog.2005.06.00739:2(171-179)Online publication date: 1-Feb-2006
https://dl.acm.org/doi/10.1016/j.patcog.2005.06.007
Gómez-Ballester EMicó LOncina J(2005)Testing some improvements of the fukunaga and narendra's fast nearest neighbour search algorithm in a spelling taskProceedings of the Second Iberian conference on Pattern Recognition and Image Analysis - Volume Part II10.1007/11492542_1(3-10)Online publication date: 7-Jun-2005
https://dl.acm.org/doi/10.1007/11492542_1
Hjaltason GSamet H(2003)Index-driven similarity search in metric spaces (Survey Article)ACM Transactions on Database Systems10.1145/958942.95894828:4(517-580)Online publication date: 1-Dec-2003
https://dl.acm.org/doi/10.1145/958942.958948
D'haes Wvan Dyck DRodet X(2003)PCA-based branch and bound search algorithms for computing K nearest neighborsPattern Recognition Letters10.1016/S0167-8655(02)00384-724:9-10(1437-1451)Online publication date: 1-Jun-2003
https://dl.acm.org/doi/10.1016/S0167-8655%2802%2900384-7
Murtagh F(2002)Clustering in massive data setsHandbook of massive data sets10.5555/779232.779247(501-543)Online publication date: 1-Jan-2002
https://dl.acm.org/doi/10.5555/779232.779247
Hjaltason GSamet H(1999)Distance browsing in spatial databasesACM Transactions on Database Systems10.1145/320248.32025524:2(265-318)Online publication date: 1-Jun-1999
https://dl.acm.org/doi/10.1145/320248.320255
Blatt MWiseman SDomany E(1997)Data Clustering Using a Model Granular MagnetNeural Computation10.1162/neco.1997.9.8.18059:8(1805-1842)Online publication date: 1-Nov-1997
https://dl.acm.org/doi/10.1162/neco.1997.9.8.1805
Show More Cited By

Abstract

Reference

Cited By

Recommendations

A Branch and Bound Algorithm for Computing k-Nearest Neighbors

PCA-based branch and bound search algorithms for computing K nearest neighbors

Extending LAESA Fast Nearest Neighbour Algorithm to Find the k Nearest Neighbours

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations