Abstract
An efficient approach to Nearest Neighbor classification is presented, which improves performance by exploiting the ability of superscalar processors to issue multiple instructions per cycle and by using the memory hierarchy adequately. This is accomplished by the use of floating-point arithmetic which outperforms integer arithmetic, and block (tiled) algorithms which exploit the data locality of programs allowing an efficient use of the data stored in the cache memory.
This work was supported by the Comissionat per a Universitats i Recerca of the Generalitat de Catalunya (BE94/Annex 3-642 and BE94-A1/110) and the Ministerio de Educación y Ciencia of Spain (TIN2004-07739-C02-01)
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Anderson, J. Dongarra, LAPACK User’s Guide, SIAM, Philadelphia, 1992.
P. Baglietto, M. Maresca, M. Migliardi, Image Processing on High-Performance RISC Systems, Proceedings of the IEEE, 84(7):917–930, July 1996.
S. Bandyopadhyay and U. Maulik Effcient prototype reordering in nearest neighbor classification, Pattern Recognition 35(12):2791–2799, Dec. 2002.
Z. Chi, J. Wu and H. Yan, Handwritten numeral recognition using self-organizing maps and fuzzy rules, Pattern Recognition, 28(1):59–66, 1995.
B.V. Dasarathy, Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques, IEEE Computer Society Press, 1991.
Digital Equip. Corp., DECchip 21064 and DECchip 21064A Alpha AXP Microprocessors-Hardware Ref. Manual, 1994.
C. Decaestecker, Finding Prototypes for Nearest Neighbor Classification by Means of Gradient Descent and Deterministic Annealing, Pattern Recognition, 30(2):281–288, 1997.
A. Djouadi, E. Bouktache, A Fast Algorithm for the Nearest-Neighbor Classifier, IEEE Trans. on Pattern Analysis and Machine Intelligence, 19(3):277–282, 1997.
J. Fu, T.S. Huang, VLSI for Pattern Recognition and Image Processing, Springer-Verlag, Berlin, 1984.
P.J. Grother, G.T. Candela and J.L. Blue, Fast Implementation of Nearest Neighbor Classifiers, Pattern Recognition, 30(3):459–465, 1997.
Y. Harnamoto, S. Uchimura and S. Tornita, A Bootstrap Technique for Nearest Neighbor Classifier Design, IEEE Trans. on Pattern Analysis and Machine Intelligence, 19(1):73–79, 1997.
R. Van Der Heiden and F.C.A. Groen, The Box-Cox Metric for Nearest Neighbor Classification Improvement, Pattern Recognition, 30(2):273–279, 1997.
Hewlett Packard, PA-RISC 1.1 Architecture and Instruction Set Reference Manual, 1994.
T. Kohonen, The self-organizing map, Proc. of the IEEE 78(9):1464–1480, 1990.
M. Kudo, N. Masuyamaa, J. Toyamaa and M. Shimbob, Simple termination conditions for k-nearest neighbor method, Pattern Recognition Letters 24(9–10):1203–1213, June 2003.
M. Lam, Software Pipelining: An Effective Technique for VLIW Machines, Proc. of the SIGPLAN’88, pp 318–328.
M.S. Lam, E.E. Rothberg and M.E. Wolf, The Cache Performance and Optimizations of Blocked Algorithms, ASPLOS 1991, pp. 67–74.
E.W. Lee and S.I. Chae, Fast Design of Reduced-Complexity Nearest-Neighbor Classifiers Using Triangular Inequality, IEEE Trans. on Pattern Analysis and Machine Intelligence, 20(5):562–566, 1998.
C.-L. Liu, H. Sako, H. Fujisawa, Performance evaluation of pattern classifiers for handwritten character recognition, Int. J. on Document Analysis and Recognition 4:191–204, 2002.
J.J. Navarro, A. Juan and T. Lang, MOB Forms: A Class of Multilevel Block Algorithms for Dense Linear Algebra Computations, ACM Int. Conf. Supercomputing, 1994, pp. 354–363.
F. Ricci and P. Avesani, Data Compression and Local Metrics for Nearest Neighbor Classification, IEEE Trans. on Pattern Analysis and Machine Intelligence, 21(4):380–384, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Herrero, J.R., Navarro, J.J. (2005). Efficient Implementation of Nearest Neighbor Classification. In: Kurzyński, M., Puchała, E., Woźniak, M., żołnierek, A. (eds) Computer Recognition Systems. Advances in Soft Computing, vol 30. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-32390-2_19
Download citation
DOI: https://doi.org/10.1007/3-540-32390-2_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25054-8
Online ISBN: 978-3-540-32390-7
eBook Packages: EngineeringEngineering (R0)