Instability results for Euclidean distance, nearest neighbor search on high dimensional Gaussian data

DOI10.1016/J.IPL.2021.106115OpenAlexW3136119811WikidataQ114167105 ScholiaQ114167105MaRDI QIDQ2032151FDOQ2032151

Authors Chris R. Giannella

Publication date 16 June 2021

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2021.106115

zbMATH Keywords

concentration of measureinformation retrievalnearest neighbor search

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• New instability results for high-dimensional nearest neighbor search
• Exact \(L_{\infty}\) nearest neighbor search in high dimensions
• Approximate nearest neighbor search in high dimensions
• Lower bounds for high dimensional nearest neighbor search and related problems
• scientific article; zbMATH DE number 2209718
• Probably correct \(k\)-nearest neighbor search in high dimensions
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• scientific article; zbMATH DE number 1775451
• scientific article; zbMATH DE number 2080487

Cites work

• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• A Strong Law for the Largest Nearest-Neighbour Link between Random Points
• Concentration of measure and cluster analysis.
• High-dimensional \(p\)-norms
• High-dimensional probability. An introduction with applications in data science
• High-dimensional statistics. A non-asymptotic viewpoint
• Indexability, concentration, and VC theory
• Introduction to Information Retrieval
• New instability results for high-dimensional nearest neighbor search
• Non-parametric detection of meaningless distances in high dimensional data
• On the behavior of intrinsically high-dimensional spaces: distances, direct and reverse nearest neighbors, and hubness
• On the geometry of similarity search: dimensionality curse and concentration of measure

Cited in

(2)

• New instability results for high-dimensional nearest neighbor search
• Rigid transformations for stabilized lower dimensional space to support subsurface uncertainty quantification and interpretation

This page was built for publication: Instability results for Euclidean distance, nearest neighbor search on high dimensional Gaussian data

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