Searching in metric spaces

By Edgar Chávez, Gonzalo Navarro, Ricardo A. Baeza-Yates, José L. Marroquín. CSUR, 2001

1,372 citations recorded by the source corpus.

Subfields: Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/fea31dc089d349565a9a140c41c841952c492453

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search (2007, neutral): “Please see [7, 15, 12] for some survey.”
Near neighbor searching with K nearest references (2015, background): “in application papers, surveys [10,16,28,50] and even books [47,57].”
Learning to Prune in Metric and Non-Metric Spaces (2013, neutral): “In metric spaces, it was proposed to compute the intrinsic dimensionality as the half of the squared signal to noise ratio (for the distance distribution) [10].”
A Complexity-Invariant Distance Measure for Time Series (2011, methodology): “The ρ-relaxed triangular inequality property implies that we can search in CID space using the same algorithms designed for metric spaces, after some scaling [4].”
Intrinsic Dimension Estimation Using Packing Numbers (2002, background): “[5] that the complexity increases with the intrinsic dimension of the data rather then with the dimension of the embedding space.”
Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching (2007, background): “…to the string-to-string correction problem we address time series similarity in light of a timeseries-to-time-series-correction problem for which the similarity between two time series is measured as the minimum cost sequence of "edit operations" needed to transform one time series into another.”
A PCA-based similarity measure for multivariate time series (2004, neutral): “Without this property, the filter and refinement phases of existing multidimensional indexing techniques cannot be utilized, because false dismissals may occur in the filter phase [3, 5, 17].”
Fast Multidimensional Entropy Estimation by $k$-d Partitioning (2009, methodology): “The naı̈ve ANN search takes Θ ( ND ) time, but improved methods exist [18].”
Rank-Based Similarity Search: Reducing the Dimensional Dependence (2015, methodology): “structures in that it makes use of the distance metric solely for ordinal pruning, thereby avoiding many of the difficulties associated with traditional approaches in high-dimensional settings, such as the loss of effectiveness of the triangle inequality for pruning search paths [12].”
The Concentration of Fractional Distances (2007, background): “Content-based data retrieval systems, for example, use the distance between a query from the user and each element in a database to retrieve the most similar data [1].”
Finding nearest neighbors in growth-restricted metrics (2002, background): “In a recent survey [4], Chávez et al.”
Comparative Analysis of Data Structures for Approximate Nearest Neighbor Search (2014, background): “(A dimensionality of a vector space is simply a number of coordinates necessary to represent a vector: This notion can be generalized to spaces without coordinates [4]).”
LOCI: fast outlier detection using the local correlation integral (2003, methodology): “There are several techniques for this [9] which use the L∞ norm on the embedding vector space1.”