Indexability, concentration, and VC theory

DOI10.1016/j.jda.2011.10.002zbMath1246.68108arXiv1008.5105OpenAlexW3103461049MaRDI QIDQ450514

Vladimir G. Pestov

Publication date: 13 September 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1008.5105

zbMATH Keywords

concentration of measurecurse of dimensionalityLipschitz functionsmetric treesexact similarity searchindexing schemespivot tablesuniform Glivenko-Cantelli theorem

Mathematics Subject Classification ID

Searching and sorting (68P10) Learning and adaptive systems in artificial intelligence (68T05) Graphical methods in statistics (62A09)

Related Items (4)

Is the \(k\)-NN classifier in high dimensions affected by the curse of dimensionality? ⋮ Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions ⋮ Distance-based index structures for fast similarity search ⋮ Instability results for Euclidean distance, nearest neighbor search on high dimensional Gaussian data

Cites Work

• On the geometry of similarity search: dimensionality curse and concentration of measure
• On the geometry of Urysohn's universal metric space
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• A short proof for a theorem of Harper about Hamming-spheres
• Remarks on finite rank projections
• Learning and generalisation. With applications to neural networks.
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• An axiomatic approach to intrinsic dimension of a dataset
• A central limit theorem for convex sets
• Ricci curvature of metric spaces
• Similarity search. The metric space approach.
• Gromov hyperbolic spaces
• The black-box complexity of nearest-neighbor search
• Lower bounds for high dimensional nearest neighbor search and related problems
• Tighter bounds for nearest neighbor search and related problems in the cell probe model
• Extensions of Lipschitz mappings into a Hilbert space
• On variants of the Johnson–Lindenstrauss lemma
• A Topological Application of the Isoperimetric Inequality
• Pivot selection techniques for proximity searching in metric spaces
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Neural Network Learning
• Geometric Representation of High Dimension, Low Sample Size Data
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Indexability, concentration, and VC theory