Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions

DOI10.1007/s00453-012-9638-2zbMath1264.68069OpenAlexW2089407614MaRDI QIDQ1950389

Vladimir G. Pestov

Publication date: 13 May 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9638-2

zbMATH Keywords

data structuressimilarity searchindexing schemesalgorithm performanceVapnik-Chernonenkis theory

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the geometry of similarity search: dimensionality curse and concentration of measure
• Indexability, concentration, and VC theory
• 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
• 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
• Foundations of multidimensional and metric data structures.
• Similarity search. The metric space approach.
• Tighter bounds for nearest neighbor search and related problems in the cell probe model
• On a model of indexability and its bounds for range queries
• Pivot selection techniques for proximity searching in metric spaces
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces

This page was built for publication: Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions