On the geometry of similarity search: Dimensionality curse and concentration of measure

Information Processing LettersPublished 1 January 2000

Vladimir Pestov

DOI10.1016/s0020-0190(99)00156-8

Source URL

Citations112

SJR quartileQ3

SJR score0.41

SNIP0.73

TL;DR

It is suggested that the curse of dimensionality affecting the similarity-based search in large datasets is a manifestation of the phenomenon of concentration of measure on high-dimensional structures.

Abstract

We suggest that the curse of dimensionality affecting the similarity-based search in large datasets is a manifestation of the phenomenon of concentration of measure on high-dimensional structures.

Keywords

Computer Science

Lecture notes in computer scienceWhen Is “Nearest Neighbor” Meaningful?

2,297 Citations1999Kevin Beyer, Jonathan Goldstein +2 more

The effect of dimensionality on the "nearest neighbor" problem is explored, and it is shown that under a broad set of conditions, as dimensionality increases, the Distance to the nearest data point approaches the distance to the farthest data point.

A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces

1,513 Citations1998Roger Weber, Hans‐Jörg Schek +1 more

It is shown formally that partitioning and clustering techniques for similarity search in HDVSs exhibit linear complexity at high dimensionality, and that existing methods are outperformed on average by a simple sequential scan if the number of dimensions exceeds around 10.

Publications mathématiques de l IHÉSConcentration of measure and isoperimetric inequalities in product spaces

862 Citations1995Michel Talagrand

Lecture notes in mathematicsAsymptotic Theory of Finite Dimensional Normed Spaces

786 Citations1986Vitali Milman, Gideon Schechtman

Information Processing LettersSatisfying general proximity / similarity queries with metric trees

698 Citations1991Jeffrey Uhlmann

Divide-and-conquer search strategies are described for satisfying proximity queries involving arbitrary distance metrics involving arbitrarydistance metrics.

Near Neighbor Search in Large Metric Spaces

553 Citations1995Sergey Brin

A data structure to solve the problem of finding approximate matches in a large database called a GNAT { Geometric Near-neighbor Access Tree} is introduced based on the philosophy that the data structure should act as a hierarchical geometrical model of the data as opposed to a simple decomposition of theData that does not use its intrinsic geometry.

A cost model for nearest neighbor search in high-dimensional data space

374 Citations1997Stefan Berchtold, Christian Böhm +2 more

A new cost model for nearest neighbor search in high-dimensional data space is developed which takes boundary effects into account and therefore also works in high dimensions and is applicable to different data distributions and index structures.

ACM Transactions on Mathematical SoftwareOptimal Expected-Time Algorithms for Closest Point Problems

314 Citations1980Jon Bentley, Bruce W. Weide +1 more

Algorithms for solving a number of closest-point problems in k- space, including nearest neighbor searching, finding all nearest neighbors, and computing planar minimum spanning trees can be implemented to solve practical problems very efficiently.

View PDF

Lecture notes in mathematicsAsymptotic Theory of Finite Dimensional Normed Spaces

299 Citations1986Milman, Vitali D, Schechtman, Gideon

A cost model for similarity queries in metric spaces

194 Citations1998Paolo Ciaccia, Marco Patella +1 more

This work insists that the distance distribution of objects can be profitably used to solve the problem of estimating CPU and I/O costs for processing range and k-nearest neighbors queries over metric spaces, and develops a concrete cost model for the M-tree access method.