Abstract
Nearest neighbour search is one of the most simple and used technique in Pattern Recognition. In this paper we are interested on tree based algorithms that only make use of the metric properties of the space. One of the most known and refereed method in this class was proposed by Fukunaga and Narendra in the 70’s.
This algorithm uses a tree that is traversed on search time and uses some elimination rules to avoid the full exploration of the tree.
This paper proposes two main contributions: two new ways for constructing the tree and two new elimination rules. As shown in the experiment section, both techniques reduce significantly the number of distance computations.
Chapter PDF
Similar content being viewed by others
References
Dasarathy, B.V.: Nearest Neighbour(NN) Norms: NN Pattern Classification Techniques. IEEE Computer Society Press, Los Alamitos (1991)
Chen, Y.S., Hung, Y.P., Fuh, C.S.: Fast Algorithm for Nearest Neighbour Search Based on a Lower Bound Tree. In: Proceedings of the 8th International Conference on Computer Vision, Vancouver, Canada, vol. 1, pp. 446–453 (2001)
Duda, R., Hart, P.: Pattern Classification and Scene Analysis. Wiley, Chichester (1973)
Fukunaga, K., Narendra, M.: A branch and bound algorithm for computing k– nearest neighbours. IEEE Trans. Computing 24, 750–753 (1975)
Kalantari, I., McDonald, G.: A data structure and an algorithm for the nearest point problem. IEEE Trans. Software Engineering 9, 631–634 (1983)
Miclet, L., Dabouz, M.: Approximate fast nearest-neighbour recognition. Pattern Recognition Letters 1, 277–285 (1983)
Micó, L., Oncina, J., Carrasco, R.C.: A fast branch and bound nearest neighbour classifier in metric spaces. Pattern Recognition Letters 17, 731–739 (1996)
Alinat, P.: Periodic progress report 4, ROARS project ESPRIT II – Number 5516. Thomson Technical Report TS ASM 93/S/EGS/NC/079 (1993)
Omachi, S., Aso, H.: A fast algorithm for a k-NN classifier based on branch and bound method and computational quantity estimation. Systems and Computers in Japan 31(6), 1–9 (2000)
Webb, G.I.: OPUS: An Efficient Admissible Algorithm for Unordered Search. Journal of Artificial Intelligence Research 3, 431–465 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gómez-Ballester, E., Micó, L., Oncina, J. (2003). Some Improvements in Tree Based Nearest Neighbour Search Algorithms. In: Sanfeliu, A., Ruiz-Shulcloper, J. (eds) Progress in Pattern Recognition, Speech and Image Analysis. CIARP 2003. Lecture Notes in Computer Science, vol 2905. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24586-5_56
Download citation
DOI: https://doi.org/10.1007/978-3-540-24586-5_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20590-6
Online ISBN: 978-3-540-24586-5
eBook Packages: Springer Book Archive
