On the geometry of similarity search: dimensionality curse and concentration of measure

DOI10.1016/S0020-0190(99)00156-8zbMath1339.68245OpenAlexW2043362380MaRDI QIDQ294719

Vladimir G. Pestov

Publication date: 16 June 2016

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

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019099001568?np=y

zbMATH Keywords

data structuresconcentration of measurecurse of dimensionalitysimilarity search

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Data structures (68P05) Classical measure theory (28A99)

Related Items (16)

Utilization of singularity exponent in nearest neighbor based classifier ⋮ Feature weighting as a tool for unsupervised feature selection ⋮ On the distance concentration awareness of certain data reduction techniques ⋮ Exploring the common principal subspace of deep features in neural networks ⋮ An axiomatic approach to intrinsic dimension of a dataset ⋮ Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions ⋮ Indexability, concentration, and VC theory ⋮ Concentration of measure and cluster analysis. ⋮ The encounter of interval and probabilistic approaches to structural reliability at the design point ⋮ When is `nearest neighbour' meaningful: A converse theorem and implications ⋮ Unnamed Item ⋮ New instability results for high-dimensional nearest neighbor search ⋮ Instability results for Euclidean distance, nearest neighbor search on high dimensional Gaussian data ⋮ Extreme-value-theoretic estimation of local intrinsic dimensionality ⋮ A survey on unsupervised outlier detection in high‐dimensional numerical data ⋮ Intrinsic dimension of geometric data sets

Cites Work

• Unnamed Item
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Satisfying general proximity/similarity queries with metric trees
• Concentration of measure and isoperimetric inequalities in product spaces
• A Topological Application of the Isoperimetric Inequality
• Optimal Expected-Time Algorithms for Closest Point Problems

This page was built for publication: On the geometry of similarity search: dimensionality curse and concentration of measure