On the geometry of similarity search: dimensionality curse and concentration of measure
From MaRDI portal
Publication:294719
DOI10.1016/S0020-0190(99)00156-8zbMath1339.68245OpenAlexW2043362380MaRDI QIDQ294719
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
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