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

Summary: Formal analysis shows HDVS partitioning methods have linear complexity and degrade beyond ~10 dimensions; sequential scans often win. It proposes VA-file, an approximate vector-encoding, comparing with R*-tree and X-tree, and shows near-sequential speed. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8489
Venue: VLDB
Year: 1998
Pagerank: 0.00044673733
Overall Rank: 48 | 99.67%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 96 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
23	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00055560094
114	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00032660283
152	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00029288871
226	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.00024196346
309	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002181162
319	On The Marriage of Lp-norms and Edit Distance	2004	VLDB	0.00021432452
472	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.0001798859
476	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00017896807
592	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.0001605665
615	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015854124
723	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014720507
957	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013044785
1,018	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00012687864
1,268	Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials	2004	SIGMOD	0.00011492365
1,275	Continuous Nearest Neighbor Search	2002	VLDB	0.00011473408
1,551	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00010436352
1,559	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.0001040748
1,567	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00010395417
1,580	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.00010361788
1,785	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.8401655e-05
1,938	ATLAS: A Probabilistic Algorithm for High Dimensional Similarity Search	2011	SIGMOD	9.5248884e-05
2,183	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.0672172e-05
2,199	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	9.0284127e-05
2,723	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	8.2637153e-05
2,843	Approximate NN Queries on Streams with Guaranteed Error/performance Bounds	2004	VLDB	8.1092483e-05
2,939	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	8.0039334e-05
2,989	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.9365431e-05
3,011	The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art	2019	VLDB	7.9174527e-05
3,076	General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows	2002	SIGMOD	7.8512918e-05
3,184	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	7.7301329e-05
3,230	FTW: Fast Similarity Search under the Time Warping Distance	2005	PODS	7.6910195e-05
3,367	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD	7.5433008e-05
3,419	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	7.5046513e-05
3,515	Location-based Spatial Queries	2003	SIGMOD	7.4206522e-05
3,547	Similarity Query Processing for High-Dimensional Data	2020	VLDB	7.3840679e-05
3,550	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	7.3807863e-05
3,631	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD	7.3134546e-05
3,678	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.2688557e-05
3,799	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	7.1682127e-05
4,002	Inter-Media Hashing for Large-scale Retrieval from Heterogeneous Data Sources	2013	SIGMOD	7.039633e-05
4,041	Top-k Publish-Subscribe for Social Annotation of News	2013	VLDB	7.0071716e-05
4,618	On the Complexity of Inner Product Similarity Join	2016	PODS	6.6665536e-05
4,792	Indexing Large Human-Motion Databases	2004	VLDB	6.5722054e-05
5,001	Neighbor-Sensitive Hashing	2016	VLDB	6.4747318e-05
5,066	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	6.444669e-05
5,103	Permutation Search Methods are Efficient, Yet Faster Search is Possible	2015	VLDB	6.4273601e-05
5,495	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB	6.2653095e-05
5,809	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.1420277e-05
5,848	Query-Sensitive Embeddings	2005	SIGMOD	6.1281111e-05
6,300	High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings	2020	SIGMOD	5.9827236e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020323916
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011613174
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00083860144
19	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00058633116
55	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0004086718
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035480882
284	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022500624
354	The Query By Image Content (QBIC) System	1995	SIGMOD	0.00020437323
514	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00017312868
1,132	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00012117638
1,497	On the Analysis of Indexing Schemes	1997	PODS	0.00010658678
3,843	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	7.1321477e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,796	Similarity search in the blink of an eye with compressed indices	2023	VLDB	8.178491e-05
723	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014720507
1,785	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.8401655e-05
3,843	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	7.1321477e-05
805	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00013953964
6,553	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.9006284e-05
9,212	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB	5.3651567e-05
8,545	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	5.4745332e-05
23	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00055560094
13,581	What's Wrong with High-Dimensional Similarity Search?	2008	VLDB	-