What's Wrong with High-Dimensional Similarity Search?

Summary: Analyzes why high-dimensional similarity search is intractable and shows NN search becomes linear beyond dimensionality. Proposes VA-File, a linear-search structure using approximations to speed scans; experiments show it beats hierarchies for D>5. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9652
Venue: VLDB
Year: 2008
Pagerank: -
Overall Rank: 13,568 | 5.61%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Stephen Blott
2. Roger Weber

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723
3,555	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	6.9772546e-05
5,882	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB	5.2892937e-05
825	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016228517
4,200	New Trends in High-D Vector Similarity Search: AI-driven, Progressive, and Distributed	2021	VLDB	6.3651489e-05
3,579	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9502303e-05
2,107	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5330494e-05
8,647	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4768766e-05
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144