{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T02:31:15Z","timestamp":1777775475255,"version":"3.51.4"},"reference-count":183,"publisher":"Emerald","issue":"5-6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,5,31]]},"abstract":"<jats:p>Many modern methods for prediction leverage nearest neighbor search to find past training examples most similar to a test example, an idea that dates back in text to at least the 11th century and has stood the test of time. This monograph aims to explain the success of these methods, both in theory, for which we cover foundational nonasymptotic statistical guarantees on nearest-neighbor-based regression and classification, and in practice, for which we gather prominent methods for approximate nearest neighbor search that have been essential to scaling prediction systems reliant on nearest neighbor analysis to handle massive datasets. Furthermore, we discuss connections to learning distances for use with nearest neighbor methods, including how random decision trees and ensemble methods learn nearest neighbor structure, as well as recent developments in crowdsourcing and graphons.<\/jats:p>\n                  <jats:p>In terms of theory, our focus is on nonasymptotic statistical guarantees, which we state in the form of how many training data and what algorithm parameters ensure that a nearest neighbor prediction method achieves a user-specified error tolerance. We begin with the most general of such results for nearest neighbor and related kernel regression and classification in general metric spaces. In such settings in which we assume very little structure, what enables successful prediction is smoothness in the function being estimated for regression, and a low probability of landing near the decision boundary for classification. In practice, these conditions could be difficult to verify empirically for a real dataset. We then cover recent theoretical guarantees on nearest neighbor prediction in the three case studies of time series forecasting, recommending products to people over time, and delineating human organs in medical images by looking at image patches. In these case studies, clustering structure, which is easier to verify in data and more readily interpretable by practitioners, enables successful prediction.<\/jats:p>","DOI":"10.1561\/2200000064","type":"journal-article","created":{"date-parts":[[2018,5,31]],"date-time":"2018-05-31T03:54:21Z","timestamp":1527738861000},"page":"337-588","source":"Crossref","is-referenced-by-count":89,"title":["Explaining the Success of Nearest Neighbor Methods in Prediction"],"prefix":"10.1108","volume":"10","author":[{"given":"George H.","family":"Chen","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Devavrat","family":"Shah","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","published-online":{"date-parts":[[2018,5,31]]},"reference":[{"issue":"3","key":"2025122813522967800_ref001","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1007\/s10463-006-0032-1","article-title":"On the kernel rule for function classification","volume":"58","author":"Abraham","year":"2006","journal-title":"Annals of the Institute of Statistical Mathematics"},{"issue":"1","key":"2025122813522967800_ref002","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1137\/060673096","article-title":"The fast Johnson\u2013Lindenstrauss transform and approximate nearest neighbors","volume":"39","author":"Ailon","year":"2009","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"2025122813522967800_ref003","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1016\/0047-259X(81)90099-3","article-title":"Representations for partially exchangeable arrays of random variables","volume":"11","author":"Aldous","year":"1981","journal-title":"Journal of Multivariate Analysis"},{"key":"2025122813522967800_ref004","first-page":"2773","article-title":"Tensor decompositions for learning latent variable models","volume":"15","author":"Anandkumar","year":"2014","journal-title":"Journal of Machine Learning Research"},{"key":"2025122813522967800_ref005","first-page":"4916","article-title":"k\u2217-nearest neighbors: from global to local","author":"Anava","year":"2016","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"1","key":"2025122813522967800_ref006","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1145\/1327452.1327494","article-title":"Near-optimal hashing algorithms for near neighbor problem in high dimension","volume":"51","author":"Andoni","year":"2008","journal-title":"Communications of the ACM"},{"key":"2025122813522967800_ref007","first-page":"1225","volume-title":"Ad-vances in Neural Information Processing Systems","author":"Andoni","year":"2015"},{"key":"2025122813522967800_ref008","first-page":"47","volume-title":"Symposium on Discrete Algorithms","author":"Andoni","year":"2017"},{"key":"2025122813522967800_ref009","first-page":"793","volume-title":"Symposium on Theory of Computing","author":"Andoni","year":"2015"},{"key":"2025122813522967800_ref010","author":"Andoni","year":"2015"},{"issue":"2","key":"2025122813522967800_ref011","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1214\/009053606000001217","article-title":"Fast learning rates for plug-in classifiers","volume":"35","author":"Audibert","year":"2007","journal-title":"The Annals of Statistics"},{"issue":"2\u20133","key":"2025122813522967800_ref012","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1023\/A:1013689704352","article-title":"Finite-time analysis of the multiarmed bandit problem","volume":"47","author":"Auer","year":"2002","journal-title":"Machine Learning"},{"key":"2025122813522967800_ref013","volume-title":"Notes for IAS work-shop","author":"Austin","year":"2012"},{"key":"2025122813522967800_ref014","first-page":"307","volume-title":"International Conference on Data Mining","author":"Bagnall","year":"2012"},{"issue":"7","key":"2025122813522967800_ref015","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1109\/TMI.2013.2256922","article-title":"A probabilistic patch-based label fusion model for multi-atlas segmentation with registration refinement: application to cardiac MR images","volume":"32","author":"Bai","year":"2013","journal-title":"IEEE Transactions on Medical Imaging"},{"issue":"12","key":"2025122813522967800_ref016","doi-asserted-by":"crossref","first-page":"7110","DOI":"10.1109\/TIT.2012.2216980","article-title":"Analysis of a collaborative filter based on popularity amongst neighbors","volume":"58","author":"Barman","year":"2012","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"2025122813522967800_ref017","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/1531326.1531330","article-title":"PatchMatch: a randomized correspondence algorithm for structural image editing","volume":"28","author":"Barnes","year":"2009","journal-title":"ACM Transactions on Graphics"},{"key":"2025122813522967800_ref018","first-page":"699","volume-title":"International Con-ference on Data Mining","author":"Batista","year":"2011"},{"key":"2025122813522967800_ref019","first-page":"651","volume-title":"International Conference on the World Wide Web","author":"Bawa","year":"2005"},{"key":"2025122813522967800_ref020","first-page":"103","volume-title":"Foundations of Computer Science","author":"Belkin","year":"2010"},{"key":"2025122813522967800_ref021","first-page":"35","volume-title":"KDD Cup and Workshop","author":"Bennett","year":"2007"},{"key":"2025122813522967800_ref022","volume-title":"Technical report, Stanford Linear Accelerator Center","author":"Bentley","year":"1975"},{"issue":"4","key":"2025122813522967800_ref023","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1109\/TSE.1979.234200","article-title":"Multidimensional binary search trees in database applications","author":"Bentley","year":"1979","journal-title":"IEEE Transactions on Software Engineering"},{"issue":"7","key":"2025122813522967800_ref024","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1007\/s10994-017-5633-9","article-title":"Optimal classification trees","volume":"106","author":"Bertsimas","year":"2017","journal-title":"Ma-chine Learning"},{"key":"2025122813522967800_ref025","first-page":"97","volume-title":"International Conference on Machine Learning","author":"Beygelzimer","year":"2006"},{"key":"2025122813522967800_ref026","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-25388-6","volume-title":"Lectures on the Nearest Neighbor Method","author":"Biau","year":"2015"},{"issue":"4","key":"2025122813522967800_ref027","doi-asserted-by":"crossref","first-page":"2422","DOI":"10.1214\/10-AOS800","article-title":"A deconvolution approach to estimation of a common shape in a shifted curves model","volume":"38","author":"Bigot","year":"2010","journal-title":"The Annals of Statistics"},{"key":"2025122813522967800_ref028","first-page":"4718","volume-title":"Advances in Neural Information Processing Systems","author":"Borgs","year":"2017"},{"issue":"1","key":"2025122813522967800_ref029","first-page":"1","article-title":"Dis-tributed optimization and statistical learning via the alternating direction method of multipliers","volume":"3","author":"Boyd","year":"2011","journal-title":"Foundations and Trends\u00ae in Ma-chine Learning"},{"key":"2025122813522967800_ref030","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/978-3-642-41062-8_28","volume-title":"International Conference on Similarity Search and Applications","author":"Boytsov","year":"2013"},{"issue":"1","key":"2025122813522967800_ref031","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1010933404324","article-title":"Random forests","volume":"45","author":"Breiman","year":"2001","journal-title":"Machine Learning"},{"key":"2025122813522967800_ref032","volume-title":"Clas-sification and Regression Trees","author":"Breiman","year":"1984"},{"key":"2025122813522967800_ref033","first-page":"3347","volume-title":"Advances in Neural Information Processing Systems","author":"Bresler","year":"2014"},{"key":"2025122813522967800_ref034","author":"Bresler","year":"2017"},{"key":"2025122813522967800_ref035","first-page":"207","volume-title":"SIGMETRICS Performance Evaluation Review","author":"Bresler","year":"2016"},{"key":"2025122813522967800_ref036","first-page":"737","volume-title":"Advances in Neural Information Processing Systems","author":"Bromley","year":"1994"},{"key":"2025122813522967800_ref037","first-page":"60","article-title":"A non-local algorithm for image denoising","volume":"2","author":"Buades","year":"2005","journal-title":"Computer Vision and Pattern Recognition"},{"issue":"1","key":"2025122813522967800_ref038","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000024","article-title":"Regret analysis of stochastic and nonstochastic multi-armed bandit problems","volume":"5","author":"Bubeck","year":"2012","journal-title":"Foundations and Trends\u00aein Machine Learning"},{"key":"2025122813522967800_ref039","author":"Bui","year":"2012"},{"issue":"4","key":"2025122813522967800_ref040","doi-asserted-by":"crossref","first-page":"1956","DOI":"10.1137\/080738970","article-title":"A singular value thresh-olding algorithm for matrix completion","volume":"20","author":"Cai","year":"2010","journal-title":"SIAM Journal on Opti-mization"},{"issue":"6","key":"2025122813522967800_ref041","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1109\/JPROC.2009.2035722","article-title":"Matrix completion with noise","volume":"98","author":"Candes","year":"2010","journal-title":"Proceedings of the IEEE"},{"issue":"6","key":"2025122813522967800_ref042","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","article-title":"Exact matrix completion via convex optimization","volume":"9","author":"Cand\u00e8s","year":"2009","journal-title":"Foundations of Computational Mathematics"},{"key":"2025122813522967800_ref043","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1051\/ps:2006014","article-title":"Nearest neighbor classification in infinite dimension","volume":"10","author":"C\u00e9rou","year":"2006","journal-title":"ESAIM: Probability and Statistics"},{"issue":"6","key":"2025122813522967800_ref044","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1109\/TSMCA.2007.897589","article-title":"On the time series K-nearest neighbor classification of abnormal brain activity","volume":"37","author":"Chaovalitwongse","year":"2007","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics,Part A: Systems and Humans"},{"issue":"1","key":"2025122813522967800_ref045","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1214\/14-AOS1272","article-title":"Matrix estimation by universal singular value thresholding","volume":"43","author":"Chatterjee","year":"2015","journal-title":"The Annals of Statistics"},{"key":"2025122813522967800_ref046","first-page":"3437","volume-title":"Advances in Neural Information Processing Systems","author":"Chaudhuri","year":"2014"},{"issue":"1","key":"2025122813522967800_ref047","first-page":"9","article-title":"Learning mixtures of product dis-tributions using correlations and independence","volume":"4","author":"Chaudhuri","year":"2008","journal-title":"Conference on Learning Theory"},{"key":"2025122813522967800_ref048","volume-title":"PhD thesis","author":"Chen","year":"2015"},{"key":"2025122813522967800_ref049","first-page":"1088","volume-title":"Advances in Neural Information Processing Systems","author":"Chen","year":"2013"},{"key":"2025122813522967800_ref050","first-page":"140","volume-title":"International Conference on Medical Image Computing and Computer-Assisted Intervention","author":"Chen","year":"2015"},{"key":"2025122813522967800_ref051","first-page":"539","volume-title":"Computer Vision and Pattern Recognition","author":"Chopra","year":"2005"},{"key":"2025122813522967800_ref052","doi-asserted-by":"crossref","first-page":"15","DOI":"10.7551\/mitpress\/4908.003.0005","volume-title":"Nearest-neighbor methods for learning and vision: theory and practice","author":"Clarkson","year":"2006"},{"issue":"2","key":"2025122813522967800_ref053","doi-asserted-by":"crossref","first-page":"940","DOI":"10.1016\/j.neuroimage.2010.09.018","article-title":"Patch-based segmentation using expert priors: ap-plication to hippocampus and ventricle segmentation","volume":"54","author":"Coup\u00e9","year":"2011","journal-title":"NeuroImage"},{"key":"2025122813522967800_ref054","first-page":"20","volume-title":"Current Contents","author":"Cover","year":"1982"},{"issue":"1","key":"2025122813522967800_ref055","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/TIT.1967.1053964","article-title":"Nearest neighbor pattern clas-sification","volume":"13","author":"Cover","year":"1967","journal-title":"IEEE Transactions on Information Theory"},{"issue":"9","key":"2025122813522967800_ref056","doi-asserted-by":"crossref","first-page":"1200","DOI":"10.1109\/TIP.2004.833105","article-title":"Region filling and object removal by exemplar-based image inpainting","volume":"13","author":"Criminisi","year":"2004","journal-title":"IEEE Transactions on Image Processing"},{"key":"2025122813522967800_ref057","first-page":"537","volume-title":"Symposium on Theory of Computing","author":"Dasgupta","year":"2008"},{"key":"2025122813522967800_ref058","first-page":"203","article-title":"A probabilistic analysis of EM for mixtures of separated, spherical Gaussians","volume":"8","author":"Dasgupta","year":"2007","journal-title":"Journal of Machine Learning Research"},{"issue":"1","key":"2025122813522967800_ref059","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s00453-014-9885-5","article-title":"Randomized partition trees for nearest neighbor search","volume":"72","author":"Dasgupta","year":"2015","journal-title":"Algorithmica"},{"issue":"6364","key":"2025122813522967800_ref060","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1126\/science.aam9868","article-title":"A neural algo-rithm for a fundamental computing problem","volume":"358","author":"Dasgupta","year":"2017","journal-title":"Science"},{"key":"2025122813522967800_ref061","first-page":"253","volume-title":"Sym-posium on Computational Geometry","author":"Datar","year":"2004"},{"issue":"1","key":"2025122813522967800_ref062","first-page":"1","article-title":"La pr\u00e9vision: ses lois logiques, ses sources sub-jectives","volume":"7","author":"De Finetti","year":"1937","journal-title":"Annales de l\u2019institut Henri Poincar\u00e9"},{"key":"2025122813522967800_ref063","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-642-15835-3_9","volume-title":"MICCAI Work-shop on Statistical Atlases and Computational Models of the Heart","author":"Depa","year":"2010"},{"key":"2025122813522967800_ref064","author":"Deshpande","year":"2013"},{"key":"2025122813522967800_ref065","author":"Devlin","year":"2015"},{"issue":"6","key":"2025122813522967800_ref066","doi-asserted-by":"crossref","first-page":"1310","DOI":"10.1214\/aos\/1176345647","article-title":"On the almost everywhere convergence of nonpara-metric regression function estimates","volume":"9","author":"Devroye","year":"1981","journal-title":"The Annals of Statistics"},{"issue":"3","key":"2025122813522967800_ref067","doi-asserted-by":"crossref","first-page":"1371","DOI":"10.1214\/aos\/1176325633","article-title":"On the strong universal consistency of nearest neighbor regression function estimates","volume":"22","author":"Devroye","year":"1994","journal-title":"The Annals of Statistics"},{"key":"2025122813522967800_ref068","volume":"31","author":"Devroye","year":"2013","journal-title":"A Probabilistic Theory of Pattern Recognition"},{"issue":"2","key":"2025122813522967800_ref069","doi-asserted-by":"crossref","first-page":"1542","DOI":"10.14778\/1454159.1454226","article-title":"Querying and mining of time series data: experimental comparison of representations and distance measures","volume":"1","author":"Ding","year":"2008","journal-title":"Proceedings of the VLDB Endowment"},{"key":"2025122813522967800_ref070","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs","volume":"6","author":"Erd\u0151s","year":"1959","journal-title":"Publicationes Mathematicae"},{"key":"2025122813522967800_ref071","first-page":"2142","volume-title":"Advances in Neural Information Processing Systems","author":"Feldman","year":"2011"},{"key":"2025122813522967800_ref072","volume-title":"Technical report, USAF School of Aviation Medicine","author":"Fix","year":"1951"},{"key":"2025122813522967800_ref073","volume-title":"Technical report, USAF School of Aviation Medicine","author":"Fix","year":"1952"},{"issue":"1","key":"2025122813522967800_ref074","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1023\/A:1026501619075","article-title":"Learning low-level vision","volume":"40","author":"Freeman","year":"2000","journal-title":"International Journal of Computer Vision"},{"issue":"1","key":"2025122813522967800_ref075","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1006\/jcss.1997.1504","article-title":"A decision-theoretic generaliza-tion of on-line learning and an application to boosting","volume":"55","author":"Freund","year":"1997","journal-title":"Journal of Computer and System Sciences"},{"key":"2025122813522967800_ref076","volume-title":"Introduction to Statistical Pattern Recognition (2nd ed.)","author":"Fukunaga","year":"1990"},{"issue":"3","key":"2025122813522967800_ref077","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1214\/15-AOS1395","article-title":"Classification in general finite dimensional spaces with the k-nearest neighbor uule","volume":"44","author":"Gadat","year":"2016","journal-title":"The Annals of Statistics"},{"key":"2025122813522967800_ref078","first-page":"757","volume-title":"International Conference on Machine Learning","author":"Gentile","year":"2014"},{"key":"2025122813522967800_ref079","first-page":"518","article-title":"Similarity search in high dimensions via hashing","volume":"99","author":"Gionis","year":"1999","journal-title":"International Conference on Very Large Data Bases"},{"issue":"4","key":"2025122813522967800_ref080","doi-asserted-by":"crossref","first-page":"1150","DOI":"10.3150\/08-BEJ144","article-title":"Universal pointwise selection rule in multivariate function estimation","volume":"14","author":"Goldenshluger","year":"2008","journal-title":"Bernoulli"},{"issue":"1\u20132","key":"2025122813522967800_ref081","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s00440-007-0119-5","article-title":"Structural adaptation via Lp-norm oracle inequalities","volume":"143","author":"Goldenshluger","year":"2009","journal-title":"Probability Theory and Related Fields"},{"issue":"3","key":"2025122813522967800_ref082","doi-asserted-by":"crossref","first-page":"1608","DOI":"10.1214\/11-AOS883","article-title":"Bandwidth selection in ker-nel density estimation: oracle inequalities and adaptive minimax optimality","volume":"39","author":"Goldenshluger","year":"2011","journal-title":"The Annals of Statistics"},{"issue":"2","key":"2025122813522967800_ref083","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1137\/S0040585X97985923","article-title":"General selection rule from a family of linear estimators","volume":"57","author":"Goldenshluger","year":"2013","journal-title":"Theory of Probability & Its Applications"},{"issue":"3-4","key":"2025122813522967800_ref084","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s00440-013-0512-1","article-title":"On adaptive minimax density estimation on Rd","volume":"159","author":"Goldenshluger","year":"2014","journal-title":"Probability Theory and Related Fields"},{"key":"2025122813522967800_ref085","volume-title":"Deep Learning","author":"Goodfellow","year":"2016"},{"key":"2025122813522967800_ref086","first-page":"306","volume-title":"Uncertainty in Artificial Intelligence","author":"Grosse","year":"2012"},{"key":"2025122813522967800_ref087","doi-asserted-by":"crossref","DOI":"10.1007\/b97848","volume-title":"A Distribution-Free Theory of Nonparametric Regression","author":"Gy\u00f6rfi","year":"2002"},{"issue":"5","key":"2025122813522967800_ref088","doi-asserted-by":"crossref","first-page":"2135","DOI":"10.1214\/07-AOS537","article-title":"Choice of neighbor order in nearest-neighbor classification","volume":"36","author":"Hall","year":"2008","journal-title":"The Annals of Statistics"},{"key":"2025122813522967800_ref089","first-page":"24","volume-title":"International Conference of the Cross-Language Evaluation Forum for European Languages","author":"Hanbury","year":"2012"},{"issue":"1","key":"2025122813522967800_ref090","doi-asserted-by":"crossref","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","article-title":"Approximate nearest neighbor: towards removing the curse of dimensionality","volume":"8","author":"Har-Peled","year":"2012","journal-title":"Theory of Computing"},{"issue":"4","key":"2025122813522967800_ref091","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/2827872","article-title":"The MovieLens datasets: history and context","volume":"5","author":"Harper","year":"2016","journal-title":"ACM Transactions on Interactive Intelligent Systems"},{"key":"2025122813522967800_ref092","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-84858-7","volume-title":"The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.)","author":"Hastie","year":"2009"},{"key":"2025122813522967800_ref093","volume-title":"A First Course in Coding Theory","author":"Hill","year":"1986"},{"issue":"7","key":"2025122813522967800_ref094","first-page":"321","article-title":"Algorithm 65: find","volume":"4","author":"Hoare","year":"1961","journal-title":"Communications of the ACM"},{"issue":"2","key":"2025122813522967800_ref095","first-page":"5","article-title":"Inequalities on the Lambert W function and hyperpower function","volume":"9","author":"Hoorfar","year":"2008","journal-title":"Journal of Inequalities in Pure and Applied Mathematics"},{"key":"2025122813522967800_ref096","first-page":"281","volume-title":"Exchangeability in Probability and Statis-tics","author":"Hoover","year":"1981"},{"key":"2025122813522967800_ref097","first-page":"11","volume-title":"In-novations in Theoretical Computer Science","author":"Hsu","year":"2013"},{"key":"2025122813522967800_ref098","first-page":"631","volume-title":"International Conference on Medical Image Computing and Computer-Assisted Intervention","author":"Iglesias","year":"2013"},{"key":"2025122813522967800_ref099","first-page":"604","volume-title":"Symposium on Theory of Computing","author":"Indyk","year":"1998"},{"issue":"189-206","key":"2025122813522967800_ref100","first-page":"1","article-title":"Extensions of Lipschitz mappings into a Hilbert space","volume":"26","author":"Johnson","year":"1984","journal-title":"Contemporary Mathematics"},{"issue":"23","key":"2025122813522967800_ref101","doi-asserted-by":"crossref","first-page":"2865","DOI":"10.1093\/bioinformatics\/btl512","article-title":"Application of a simple likelihood ratio approximant to protein sequence classification","volume":"22","author":"Kaj\u00e1n","year":"2006","journal-title":"Bioinformatics"},{"key":"2025122813522967800_ref102","unstructured":"Kamath, G. C.\n           (2015). \u201cBounds on the expectation of the maximum of samples from a Gaussian\u201d. url: http:\/\/www.gautamkamath.com\/ writings\/gaussian_max.pdf."},{"key":"2025122813522967800_ref103","first-page":"741","volume-title":"Symposium on Theory of Computing","author":"Karger","year":"2002"},{"issue":"6","key":"2025122813522967800_ref104","doi-asserted-by":"crossref","first-page":"2980","DOI":"10.1109\/TIT.2010.2046205","article-title":"Matrix completion from a few entries","volume":"56","author":"Keshavan","year":"2010","journal-title":"IEEE Transactions on Information Theory"},{"key":"2025122813522967800_ref105","first-page":"2057","article-title":"Matrix completion from noisy entries","volume":"11","author":"Keshavan","year":"2010","journal-title":"Journal of Machine Learning Research"},{"issue":"7538","key":"2025122813522967800_ref106","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1038\/518164a","article-title":"In retrospect: Book of Optics","author":"Al-Khalili","year":"2015","journal-title":"Nature"},{"key":"2025122813522967800_ref107","first-page":"599","volume-title":"Symposium on Theory of Computing","author":"Kleinberg","year":"1997"},{"issue":"2\u20133","key":"2025122813522967800_ref108","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10994-010-5178-7","article-title":"Regret bounds for sleeping experts and bandits","volume":"80","author":"Kleinberg","year":"2010","journal-title":"Machine Learning"},{"issue":"3","key":"2025122813522967800_ref109","doi-asserted-by":"crossref","first-page":"1266","DOI":"10.1214\/aos\/1176348769","article-title":"Statistical tools to analyze data representing a sample of curves","volume":"20","author":"Kneip","year":"1992","journal-title":"The Annals of Statistics"},{"key":"2025122813522967800_ref110","volume-title":"The Art of Computer Programming - Vol III: Sorting and Searching","author":"Knuth","year":"1973"},{"issue":"2","key":"2025122813522967800_ref111","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/j.jmva.2005.03.006","article-title":"Rates of convergence for partitioning and nearest neighbor regression estimates with unbounded data","volume":"97","author":"Kohler","year":"2006","journal-title":"Journal of Multivariate Analysis"},{"key":"2025122813522967800_ref112","first-page":"480","volume-title":"Artificial Intelligence and Statistics","author":"Kontorovich","year":"2015"},{"key":"2025122813522967800_ref113","first-page":"131","volume-title":"International Conference on Medical Image Computing and Computer-Assisted Intervention","author":"Konukoglu","year":"2013"},{"key":"2025122813522967800_ref114","unstructured":"Koren, Y.\n           (2009). \u201cThe BellKor Solution to the Netflix Grand Prize\u201d. url:http:\/\/www.netflixprize.com\/assets\/GrandPrize2009_BPC_ BellKor.pdf."},{"key":"2025122813522967800_ref115","first-page":"729","volume-title":"Advances in Neural Information Processing Systems","author":"Kpotufe","year":"2011"},{"key":"2025122813522967800_ref116","first-page":"3075","volume-title":"Advances in Neural Information Processing Systems","author":"Kpotufe","year":"2013"},{"issue":"5","key":"2025122813522967800_ref117","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1109\/TIT.1986.1057226","article-title":"The rates of convergence on kernel regression esti-mates and classification rules","volume":"32","author":"Krzy\u017cak","year":"1986","journal-title":"IEEE Transactions on Information Theory"},{"key":"2025122813522967800_ref118","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0378-3758(87)90065-6","article-title":"The pointwise rate of convergence of the kernel regression estimate","volume":"16","author":"Krzy\u017cak","year":"1987","journal-title":"Journal of Statistical Planning and Inference"},{"issue":"4","key":"2025122813522967800_ref119","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1561\/2200000019","article-title":"Metric learning: a survey","volume":"5","author":"Kulis","year":"2013","journal-title":"Foundations and Trends\u00ae in Machine Learning"},{"key":"2025122813522967800_ref120","first-page":"2155","volume-title":"Advances in Neural Information Processing Systems","author":"Lee","year":"2016"},{"key":"2025122813522967800_ref121","first-page":"1781","author":"Lee","year":"2013","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"1","key":"2025122813522967800_ref122","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.dss.2011.12.014","article-title":"Nearest-neighbor-based approach to time-series classification","volume":"53","author":"Lee","year":"2012","journal-title":"Decision Sup-port Systems"},{"issue":"2","key":"2025122813522967800_ref123","first-page":"123","article-title":"Adaptive minimax estimation of infinitely differentiable functions","volume":"7","author":"Lepski","year":"1998","journal-title":"Mathematical Methods of Statis-tics"},{"issue":"3","key":"2025122813522967800_ref124","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1214\/aos\/1069362731","article-title":"Optimal spatial adaptation to inhomogeneous smoothness: an approach based on kernel estimates with variable bandwidth selectors","volume":"25","author":"Lepski","year":"1997","journal-title":"The Annals of Statistics"},{"issue":"6","key":"2025122813522967800_ref125","doi-asserted-by":"crossref","first-page":"2512","DOI":"10.1214\/aos\/1030741083","article-title":"Optimal pointwise adaptive methods in nonparametric estimation","volume":"25","author":"Lepski","year":"1997","journal-title":"The Annals of Statistics"},{"issue":"6","key":"2025122813522967800_ref126","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1038\/scientificamerican0666-42","article-title":"Molecular model-building by computer","volume":"214","author":"Levinthal","year":"1966","journal-title":"Scien-tific American"},{"issue":"474","key":"2025122813522967800_ref127","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1198\/016214505000001230","article-title":"Random forests and adaptive nearest neighbors","volume":"101","author":"Lin","year":"2006","journal-title":"Journal of the American Statistical Association"},{"issue":"1","key":"2025122813522967800_ref128","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1109\/MIC.2003.1167344","article-title":"Amazon.com recommenda-tions: item-to-item collaborative filtering","volume":"7","author":"Linden","year":"2003","journal-title":"IEEE Internet Comput-ing"},{"key":"2025122813522967800_ref129","first-page":"825","volume-title":"Advances in Neural Information Processing Systems","author":"Liu","year":"2005"},{"key":"2025122813522967800_ref130","volume":"60","author":"Lov\u00e1sz","year":"2012","journal-title":"Large Networks and Graph Limits"},{"issue":"6","key":"2025122813522967800_ref131","doi-asserted-by":"crossref","first-page":"933","DOI":"10.1016\/j.jctb.2006.05.002","article-title":"Limits of dense graph sequences","volume":"96","author":"Lov\u00e1sz","year":"2006","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"6","key":"2025122813522967800_ref132","doi-asserted-by":"crossref","first-page":"1808","DOI":"10.1214\/aos\/1017939240","article-title":"Smooth discrimination analysis","volume":"27","author":"Mammen","year":"1999","journal-title":"The Annals of Statistics"},{"key":"2025122813522967800_ref133","first-page":"2864","volume-title":"AAAI Conference on Artificial Intelligence","author":"Mathy","year":"2015"},{"key":"2025122813522967800_ref134","first-page":"2287","article-title":"Spectral regular-ization algorithms for learning large incomplete matrices","volume":"11","author":"Mazumder","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"2025122813522967800_ref135","first-page":"93","volume-title":"Foundations of Computer Science","author":"Moitra","year":"2010"},{"issue":"4","key":"2025122813522967800_ref136","doi-asserted-by":"crossref","first-page":"930","DOI":"10.1137\/050646858","article-title":"Lower bounds on locality sensitive hashing","volume":"21","author":"Motwani","year":"2007","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"331\u2013340","key":"2025122813522967800_ref137","first-page":"2","article-title":"Fast approximate nearest neighbors with automatic algorithm configuration","volume":"2","author":"Muja","year":"2009","journal-title":"International Conference on Computer Vision Theory and Application"},{"issue":"11","key":"2025122813522967800_ref138","doi-asserted-by":"crossref","first-page":"2227","DOI":"10.1109\/TPAMI.2014.2321376","article-title":"Scalable nearest neighbor algorithms for high dimensional data","volume":"36","author":"Muja","year":"2014","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"1","key":"2025122813522967800_ref139","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1137\/1109020","article-title":"On estimating regression","volume":"9","author":"Nadaraya","year":"1964","journal-title":"Theory of Proba-bility & Its Applications"},{"issue":"3","key":"2025122813522967800_ref140","first-page":"49","article-title":"Feature-based classification of time-series data","volume":"10","author":"Nanopoulos","year":"2001","journal-title":"International Journal of Computer Research"},{"key":"2025122813522967800_ref141","author":"Nikolov","year":"2012"},{"issue":"1","key":"2025122813522967800_ref142","first-page":"5","article-title":"Optimal lower bounds for locality-sensitive hashing (except when q is tiny)","volume":"6","author":"O\u2019Donnell","year":"2014","journal-title":"ACM Transac-tions on Computation Theory"},{"key":"2025122813522967800_ref143","volume-title":"Nearest Neighbor Search: A Database Perspective","author":"Papadopoulos","year":"2005"},{"key":"2025122813522967800_ref144","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.patrec.2013.10.022","article-title":"Alhazen and the nearest neighbor rule","volume":"38","author":"Pelillo","year":"2014","journal-title":"Pattern Recognition Letters"},{"key":"2025122813522967800_ref145","unstructured":"Piotte, M. and M.Chabbert (2009). \u201cThe Pragmatic Theory solution to the Netflix Grand Prize\u201d. url:http:\/\/www.netflixprize.com\/ assets\/GrandPrize2009_BPC_PragmaticTheory.pdf."},{"key":"2025122813522967800_ref146","volume-title":"C4.5: Programs for Machine Learning","author":"Quinlan","year":"1993"},{"key":"2025122813522967800_ref147","first-page":"3413","article-title":"A simpler approach to matrix completion","volume":"12","author":"Recht","year":"2011","journal-title":"Journal of Machine Learning Research"},{"key":"2025122813522967800_ref148","first-page":"175","volume-title":"Conference on Computer Supported Cooperative Work","author":"Resnick","year":"1994"},{"key":"2025122813522967800_ref149","first-page":"548","volume-title":"Symposium on Applied Computing","author":"Rodr\u00edguez","year":"2004"},{"issue":"10","key":"2025122813522967800_ref150","doi-asserted-by":"crossref","first-page":"1852","DOI":"10.1109\/TMI.2011.2156806","article-title":"A supervised patch-based approach for human brain labeling","volume":"30","author":"Rousseau","year":"2011","journal-title":"IEEE Transactions on Medical Imaging"},{"key":"2025122813522967800_ref151","first-page":"346","volume-title":"International Symposium on Biomedical Imaging","author":"Rousseau","year":"2013"},{"issue":"10","key":"2025122813522967800_ref152","doi-asserted-by":"crossref","first-page":"1714","DOI":"10.1109\/TMI.2010.2050897","article-title":"A generative model for image segmentation based on label fusion","volume":"29","author":"Sabuncu","year":"2010","journal-title":"IEEE Transactions on Medical Imaging"},{"issue":"1","key":"2025122813522967800_ref153","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/TASSP.1978.1163055","article-title":"Dynamic programming algorithm optimization for spoken word recognition","volume":"26","author":"Sakoe","year":"1978","journal-title":"IEEE Transactions on Acoustics, Speech, and Signal Processing"},{"issue":"7","key":"2025122813522967800_ref154","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1016\/S0167-8655(02)00225-8","article-title":"Analysis of new techniques to obtain quality training sets","volume":"24","author":"S\u00e1nchez","year":"2003","journal-title":"Pattern Recognition Letters"},{"key":"2025122813522967800_ref155","volume-title":"Baseball Prospectus 2003","author":"Silver","year":"2003"},{"key":"2025122813522967800_ref156","volume-title":"FiveThirtyEight.com","author":"Silver","year":"2008"},{"key":"2025122813522967800_ref157","first-page":"1","volume-title":"Philadel-phia: American Philosophical Society","author":"Smith","year":"2001"},{"key":"2025122813522967800_ref158","first-page":"2690","volume-title":"International Joint Conference on Neural Networks","author":"Smith","year":"2011"},{"key":"2025122813522967800_ref159","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/978-3-319-02126-3_3","volume-title":"MICCAI Workshop on Multimodal Brain Image Analysis","author":"Sridharan","year":"2013"},{"issue":"4","key":"2025122813522967800_ref160","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1214\/aos\/1176343886","article-title":"Consistent nonparametric regression","volume":"5","author":"Stone","year":"1977","journal-title":"The Annals of Statistics"},{"issue":"14","key":"2025122813522967800_ref161","doi-asserted-by":"crossref","first-page":"1930","DOI":"10.14778\/2556549.2556574","article-title":"Streaming similarity search over one billion Tweets using parallel locality-sensitive hashing","volume":"6","author":"Sundaram","year":"2013","journal-title":"Proceedings of the VLDB Endowment"},{"key":"2025122813522967800_ref162","first-page":"1821","volume-title":"Advances in Neural Information Processing Systems","author":"Sutskever","year":"2009"},{"key":"2025122813522967800_ref163","volume-title":"Reinforcement Learning: An Introduction","author":"Sutton","year":"1998"},{"key":"2025122813522967800_ref164","first-page":"105","volume-title":"Inter-national Conference on Medical Image Computing and Computer-Assisted Intervention","author":"Ta","year":"2014"},{"key":"2025122813522967800_ref165","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1093\/biomet\/25.3-4.285","article-title":"On the likelihood that one unknown prob-ability exceeds another in view of the evidence of two samples","volume":"25","author":"Thompson","year":"1933","journal-title":"Biometrika"},{"key":"2025122813522967800_ref166","unstructured":"T\u00f6scher, A. and M.Jahrer (2009). \u201cThe BigChaos Solution to the Netflix Grand Prize\u201d. url:http:\/\/www.netflixprize.com\/assets\/ GrandPrize2009_BPC_BigChaos.pdf."},{"issue":"1","key":"2025122813522967800_ref167","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1214\/aos\/1079120131","article-title":"Optimal aggregation of classifiers in statistical learning","volume":"32","author":"Tsybakov","year":"2004","journal-title":"The Annals of Statistics"},{"key":"2025122813522967800_ref168","doi-asserted-by":"crossref","DOI":"10.1007\/b13794","volume-title":"Introduction to Nonparametric Estimation","author":"Tsybakov","year":"2009"},{"issue":"4","key":"2025122813522967800_ref169","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1016\/j.jcss.2003.11.008","article-title":"A spectral algorithm for learning mixture models","volume":"68","author":"Vempala","year":"2004","journal-title":"Journal of Computer and System Sciences"},{"issue":"7","key":"2025122813522967800_ref170","doi-asserted-by":"crossref","first-page":"1492","DOI":"10.1109\/TBME.2016.2603119","article-title":"Effi-cient descriptor-based segmentation of parotid glands with nonlocal means","volume":"64","author":"Wachinger","year":"2017","journal-title":"IEEE Transactions on Biomedical Engineering"},{"key":"2025122813522967800_ref171","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/j.neuroimage.2017.02.035","article-title":"DeepNAT: deep convo-lutional neural network for segmenting neuroanatomy","volume":"170","author":"Wachinger","year":"2018","journal-title":"NeuroImage"},{"issue":"3","key":"2025122813522967800_ref172","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1214\/aos\/1069362747","article-title":"Alignment of curves by dynamic time warping","volume":"25","author":"Wang","year":"1997","journal-title":"The Annals of Statistics"},{"key":"2025122813522967800_ref173","author":"Wang","year":"2017"},{"key":"2025122813522967800_ref174","first-page":"359","article-title":"Smooth regression analysis","volume":"26","author":"Watson","year":"1964","journal-title":"Sankhy\u00afa: The Indian Journal of Statistics, Series A"},{"key":"2025122813522967800_ref175","first-page":"207","article-title":"Distance metric learning for large margin nearest neighbor classification","volume":"10","author":"Weinberger","year":"2009","journal-title":"Journal of Machine Learning Research"},{"key":"2025122813522967800_ref176","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1109\/TSMC.1972.4309137","article-title":"Asymptotic properties of nearest neighbor rules using edited data","volume":"3","author":"Wilson","year":"1972","journal-title":"IEEE Transactions on Systems, Man, and Cy-bernetics"},{"issue":"1","key":"2025122813522967800_ref177","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10115-007-0114-2","article-title":"Top 10 algorithms in data mining","volume":"14","author":"Wu","year":"2008","journal-title":"Knowledge and Information Systems"},{"key":"2025122813522967800_ref178","first-page":"324","volume-title":"Conference on Information and Knowledge Management","author":"Wu","year":"2004"},{"key":"2025122813522967800_ref179","first-page":"1033","volume-title":"International Conference on Machine Learning","author":"Xi","year":"2006"},{"key":"2025122813522967800_ref180","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/j.neuroimage.2017.04.018","article-title":"A comparison of accurate automatic hippocampal segmentation methods","volume":"155","author":"Zandifar","year":"2017","journal-title":"NeuroImage"},{"key":"2025122813522967800_ref181","author":"Zoran","year":"2017"},{"key":"2025122813522967800_ref182","first-page":"479","volume-title":"International Conference on Computer Vision","author":"Zoran","year":"2011"},{"key":"2025122813522967800_ref183","first-page":"1736","volume-title":"Advances in Neural Information Processing Systems","author":"Zoran","year":"2012"}],"container-title":["Foundations and Trends\u00ae in Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftmal\/article-pdf\/10\/5-6\/337\/11154176\/2200000064en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftmal\/article-pdf\/10\/5-6\/337\/11154176\/2200000064en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:10:43Z","timestamp":1777486243000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftmal\/article\/10\/5-6\/337\/1332393\/Explaining-the-Success-of-Nearest-Neighbor-Methods"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,31]]},"references-count":183,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2018,5,31]]}},"URL":"https:\/\/doi.org\/10.1561\/2200000064","relation":{},"ISSN":["1935-8237","1935-8245"],"issn-type":[{"value":"1935-8237","type":"print"},{"value":"1935-8245","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,31]]}}}