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

DOI10.1007/S00453-012-9638-2MaRDI QIDQ1950389zbMATH OpenOpenAlexFDO

Authors 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

algorithm performancedata structuresindexing schemessimilarity searchVapnik-Chernonenkis theory

Mathematics Subject Classification ID

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

Recommendations

• Indexability, concentration, and VC theory
• scientific article; zbMATH DE number 1893567
• Lower bounds for high dimensional nearest neighbor search and related problems
• scientific article; zbMATH DE number 2209718
• Probabilistic proximity search: Fighting the curse of dimensionality in metric spaces.

Cites work

• An axiomatic approach to intrinsic dimension of a dataset
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Foundations of multidimensional and metric data structures.
• scientific article; zbMATH DE number 437556 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 2109363 (Why is no real title available?)
• scientific article; zbMATH DE number 2209718 (Why is no real title available?)
• Indexability, concentration, and VC theory
• Indexing schemes for similarity search: an illustrated paradigm
• Learning and generalisation. With applications to neural networks.
• On a model of indexability and its bounds for range queries
• On the geometry of similarity search: dimensionality curse and concentration of measure
• Pivot selection techniques for proximity searching in metric spaces
• Satisfying general proximity/similarity queries with metric trees
• Similarity search. The metric space approach.
• The concentration of measure phenomenon
• Tighter bounds for nearest neighbor search and related problems in the cell probe model

Cited in

(1)

• Satisfying general proximity/similarity queries with metric trees

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

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