Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions
type: Item
instance of: scholarly article
title: Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions
zbMATH Open document ID: 1264.68069
author: Vladimir G. Pestov
published in: Algorithmica
publication date: 2013-05-13T00:00:00Z
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6162391
zbMATH Keywords: data structures
zbMATH Keywords: indexing schemes
zbMATH Keywords: similarity search
zbMATH Keywords: Vapnik-Chernonenkis theory
zbMATH Keywords: algorithm performance
MaRDI profile type: Publication
full work available at URL: s00453-012-9638-2
OpenAlex ID: W2089407614
cites work: Tighter bounds for nearest neighbor search and related problems in the cell probe model
cites work: Q5692700
cites work: Pivot selection techniques for proximity searching in metric spaces
cites work: Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
cites work: On a model of indexability and its bounds for range queries
cites work: Q4542583
cites work: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
cites work: The concentration of measure phenomenon
cites work: Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
cites work: On the geometry of similarity search: dimensionality curse and concentration of measure
cites work: An axiomatic approach to intrinsic dimension of a dataset
cites work: Indexability, concentration, and VC theory
cites work: Q5480639
cites work: Foundations of multidimensional and metric data structures.
cites work: Satisfying general proximity/similarity queries with metric trees
cites work: Q4261789
cites work: Q4821981
cites work: Learning and generalisation. With applications to neural networks.
cites work: Q3140435
cites work: Similarity search. The metric space approach.
DOI: 10.1007/S00453-012-9638-2
description: scientific article; zbMATH DE number 6162391