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

By R. Weber, H. Schek, Stephen Blott. 1998

Subfields: Information Retrieval & Search, Algorithms & Complexity

How researchers see this paper

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

In Information Retrieval & Search

In Algorithms & Complexity

Citations in the corpus

Product Quantization for Nearest Neighbor Search (2011, background): “However, for high dimensions it turns out [6] that such approaches are not more efﬁcient than the brute-force exhaustive distance calculation, whose complexity is O ( nD ) .”
Billion-Scale Similarity Search with GPUs (2017, background): “Such applications must deal with the curse of dimensionality [46], rendering both exhaustive search or exact indexing for non-exhaustive search impractical on billion-scale databases.”
Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “For example, [24] showed that techniques based on space partitioning degrade to linear search, even for dimensions as small as 10 or 20.”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, background): “Worse still, the exponential dependence of space and/or time on the dimension (called “curse of dimensionality”) has been observed in practice as well [WSB98].”
On the Surprising Behavior of Distance Metrics in High Dimensional Spaces (2001, background): “For example, the performance of similarity indexing structures in high dimensions degrades rapidly, so that each query requires the access of almost all the data [1].”
The Faiss Library (2024, unknown): “However, in large dimensions they provide no speedup over brute force search [50].”
Learning to Prune in Metric and Non-Metric Spaces (2013, background): “increases, the filtering efficiency of space-partitioning methods decreases rapidly, which is known as the “curse of dimensionality” [30].”
Similarity Search in High Dimensions via Hashing (1999, background): “In particular, it was shown in [45] that, both empirically and theoretically, all current indexing techniques (based on space partitioning) degrade to linear search for su(cid:14)ciently high dimensions.”
Discovering similar multidimensional trajectories (2002, methodology): “This behavior follows again the same pattern of high dimensional indexing methods [6, 36].”
The Concentration of Fractional Distances (2007, background): “[40] proposes a review of counterintuitive properties of high-dimensional geometrical spaces and relates them to the losses of performances.”
Permutation Search Methods are Efficient, Yet Faster Search is Possible (2015, methodology): “Experiments showed that exact methods can rarely outperform the sequential scan when dimensionality exceeds ten [43].”
Two-Stream Deep Hashing With Class-Specific Centers for Supervised Image Search (2020, methodology): “Experiments show that exact methods can rarely outperform the brute-force linear scan method when dimensionality is high [25].”