When is `nearest neighbour' meaningful: A converse theorem and implications

DOI10.1016/J.JCO.2009.02.011MaRDI QIDQ2272155zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Robert J. Durrant, Ata Kabán

Publication date 6 August 2009

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2009.02.011

zbMATH Keywords

latent variable modelshigh dimensionalitydistance concentration

Mathematics Subject Classification ID

Foundations and philosophical topics in statistics (62A01)

Recommendations

• A note on the asymptotic behaviour of the distance of the k_nth nearest neighbour
• On the probability that a random point is the jth nearest neighbour to its own kth nearest neighbour
• On approximate nearest neighbors under \(l_\infty\) norm
• A note on the nearest neighbor in growth-restricted metrics
• On conditional distributions of nearest neighbors
• A computationally efficient approximation to the nearest neighbor interchange metric

Cites work

• scientific article; zbMATH DE number 3934234 (Why is no real title available?)
• scientific article; zbMATH DE number 2080487 (Why is no real title available?)
• scientific article; zbMATH DE number 1391242 (Why is no real title available?)
• A First Look at Rigorous Probability Theory
• On the geometry of similarity search: dimensionality curse and concentration of measure

Cited in

(13)

• New instability results for high-dimensional nearest neighbor search
• Hubs in space: popular nearest neighbors in high-dimensional data
• scientific article; zbMATH DE number 2080487 (Why is no real title available?)
• Is the \(k\)-NN classifier in high dimensions affected by the curse of dimensionality?
• Minkowski-type distances in approximate query searches
• Random projection-based auxiliary information can improve tree-based nearest neighbor search
• On the behavior of intrinsically high-dimensional spaces: distances, direct and reverse nearest neighbors, and hubness
• On the distance concentration awareness of certain data reduction techniques
• Non-parametric detection of meaningless distances in high dimensional data
• Distance geometry and data science
• The hubness phenomenon: fact or artifact?
• On some transformations of high dimension, low sample size data for nearest neighbor classification
• A survey on unsupervised outlier detection in high‐dimensional numerical data

Describes a project that uses

Uses Software

• boost

This page was built for publication: When is `nearest neighbour' meaningful: A converse theorem and implications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272155)