{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T20:22:38Z","timestamp":1776284558517,"version":"3.50.1"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,7,13]],"date-time":"2021-07-13T00:00:00Z","timestamp":1626134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Science Foundation Ireland through I-From: The SFI Centre for Advance Manufacturing Research","award":["16\/RC\/3872"],"award-info":[{"award-number":["16\/RC\/3872"]}]},{"name":"SFI Centre for Research Training in Machine Learning","award":["18\/CRT\/6183"],"award-info":[{"award-number":["18\/CRT\/6183"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>Perhaps the most straightforward classifier in the arsenal or Machine Learning techniques is the Nearest Neighbour Classifier\u2014classification is achieved by identifying the nearest neighbours to a query example and using those neighbours to determine the class of the query. This approach to classification is of particular importance, because issues of poor runtime performance is not such a problem these days with the computational power that is available. This article presents an overview of techniques for Nearest Neighbour classification focusing on: mechanisms for assessing similarity (distance), computational issues in identifying nearest neighbours, and mechanisms for reducing the dimension of the data.<\/jats:p><jats:p>This article is the second edition of a paper previously published as a technical report [16]. Sections on similarity measures for time-series, retrieval speedup, and intrinsic dimensionality have been added. An Appendix is included, providing access to Python code for the key methods.<\/jats:p>","DOI":"10.1145\/3459665","type":"journal-article","created":{"date-parts":[[2021,7,13]],"date-time":"2021-07-13T16:48:08Z","timestamp":1626194888000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":707,"title":["k-Nearest Neighbour Classifiers - A Tutorial"],"prefix":"10.1145","volume":"54","author":[{"given":"P\u00e1draig","family":"Cunningham","sequence":"first","affiliation":[{"name":"School of Computer Science, University College Dublin"}]},{"given":"Sarah Jane","family":"Delany","sequence":"additional","affiliation":[{"name":"School of Computer Science, Technological University Dublin"}]}],"member":"320","published-online":{"date-parts":[[2021,7,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00153759"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1080\/00031305.1992.10475879","article-title":"An introduction to kernel and nearest-neighbor nonparametric regression","volume":"46","author":"Altman Naomi S.","year":"1992","journal-title":"Amer. Statist."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190645"},{"key":"e_1_2_1_4_1","volume-title":"Joint Conference on Information Sciences. 824--827","author":"Baek Kyungim","year":"2002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0483-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.234200"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2188385.2188395"},{"key":"e_1_2_1_9_1","volume-title":"Annoy: Approximate Nearest Neighbors in C++\/Python.","author":"Bernhardsson Erik","year":"2018"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_11_1","volume-title":"Survey of nearest neighbor techniques. arXiv preprint arXiv:1007.0085","author":"\u00a0al Nitin Bhatia","year":"2010"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014043630878"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-307-3.50009-5"},{"key":"e_1_2_1_14_1","volume-title":"5th Australian Joint Conference on Artificial Intelligence. World Scientific, 368--373","author":"Cameron-Jones R. Mike","year":"1992"},{"key":"e_1_2_1_15_1","volume-title":"Machine Learning Techniques for Multimedia","author":"Cunningham P\u00e1draig"},{"key":"e_1_2_1_16_1","volume-title":"Technical Report UCD-CSI-2007-4. School of Computer Science & Informatics","author":"Cunningham Padraig"},{"key":"e_1_2_1_17_1","volume-title":"Nearest Neighbor (NN) Norms: Nn Pattern Classification Techniques","author":"Dasarathy Belur V."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374452"},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"metric-learn: Metric learning algorithms in Python","volume":"21","author":"de Vazelhes William","year":"2020","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1037\/met0000079"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Sarah Jane Delany and Derek Bridge. 2007. Catching the drift: Using feature-free case-based reasoning for spam filtering. In Case-based Reasoning Research and Development Rosina O. Weber and Michael M. Richter (Eds.). Springer Berlin 314--328. Sarah Jane Delany and Derek Bridge. 2007. Catching the drift: Using feature-free case-based reasoning for spam filtering. In Case-based Reasoning Research and Development Rosina O. Weber and Michael M. Richter (Eds.). Springer Berlin 314--328.","DOI":"10.1007\/978-3-540-74141-1_22"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28631-8_11"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1975.224297"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.142"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1972.1054809"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054155"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014077"},{"key":"e_1_2_1_29_1","volume-title":"Pazzani","author":"Keogh Eamonn J.","year":"2001"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258653"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00043-X"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729694"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88688-4_27"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.838101"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Jessica Lin Eamonn Keogh Stefano Lonardi and Bill Chiu. 2003. A symbolic representation of time series with implications for streaming algorithms.In 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. DOI:DOI:https:\/\/doi.org\/10.1145\/882082.882086 Jessica Lin Eamonn Keogh Stefano Lonardi and Bill Chiu. 2003. A symbolic representation of time series with implications for streaming algorithms.In 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. DOI:DOI:https:\/\/doi.org\/10.1145\/882082.882086","DOI":"10.1145\/882082.882086"},{"key":"e_1_2_1_36_1","volume-title":"International Conference on Advances in Neural Information Processing Systems. 825--832","author":"Liu Ting"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29249-2_19"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/3006433.3006447"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0026677"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27868-9_111"},{"key":"e_1_2_1_41_1","volume-title":"5: Programs for Machine Learning","author":"Quinlan J. Ross"},{"key":"e_1_2_1_42_1","volume-title":"Mar.","author":"Reunanen Juha","year":"2003"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055464"},{"key":"e_1_2_1_44_1","volume-title":"ARPA Image Understanding Workshop","volume":"661","author":"Rubner Yossi","year":"1997"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0020623"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247656"},{"key":"e_1_2_1_48_1","volume-title":"Toward a universal law of generalization. Science 242, 4880","author":"Shepard Roger N.","year":"1988"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587638"},{"key":"e_1_2_1_50_1","volume-title":"14th International Joint Conference on Artificial Intelligence. 377--382","author":"Smyth Barry"},{"key":"e_1_2_1_51_1","volume-title":"Tslearn: A machine learning toolkit dedicated to time-series data.","author":"Tavenard Romain","year":"2017"},{"key":"e_1_2_1_52_1","first-page":"448","article-title":"An experiment with the edited nearest-neighbor rule","volume":"6","author":"Tomek Ivan","year":"1976","journal-title":"IEEE Trans. Syst., Man, Cyber."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0356-z"},{"key":"e_1_2_1_54_1","volume-title":"Saul","author":"Weinberger Kilian Q.","year":"2009"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1972.4309137"},{"key":"e_1_2_1_56_1","volume-title":"International Conference on Machine Learning","volume":"97","author":"Randall Wilson D."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007626913721"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-247-2.50066-8"},{"key":"e_1_2_1_59_1","volume-title":"International Joint Conference on Artificial Intelligence","volume":"99","author":"Zhu Jun","year":"1999"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459665","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459665","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:50Z","timestamp":1750193330000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459665"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,13]]},"references-count":59,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3459665"],"URL":"https:\/\/doi.org\/10.1145\/3459665","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,13]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}