Adaptive Indexing in High-Dimensional Metric Spaces

Summary: Introduces AV-tree: an adaptive high-dimensional metric index that reuses computed distances and uses query centers as vantage points, avoiding hyperrectangular partitions. Much lower cumulative cost for the first hundreds–thousands of queries; converges to or outperforms MVP-tree, ideal when queries are few or data changes rapidly. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13100
Venue: VLDB
Year: 2023
Pagerank: 4.3589837e-05
Overall Rank: 9,288 | 35.45%
DOI: 10.14778/3603581.3603592

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,111	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,718	Cracking Vector Search Indexes	2025	VLDB	4.1905499e-05
10,754	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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.0032118946
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00051785122
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030020929
407	Database Cracking	2007	CIDR	0.00023941779
2,231	Self-organizing Tuple Reconstruction in Column-stores	2009	SIGMOD	9.2367968e-05
2,361	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9648608e-05
2,979	The Uncracked Pieces in Database Cracking	2014	VLDB	7.7833926e-05
3,780	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	6.7703467e-05
3,897	Updating a Cracked Database	2007	SIGMOD	6.6526754e-05
4,507	Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores	2012	VLDB	6.1271582e-05
5,086	Pivot-based Metric Indexing	2017	VLDB	5.7036022e-05
6,203	k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation	2016	VLDB	5.1552752e-05
7,000	Progressive Indexes: Indexing for Interactive Data Analysis	2019	VLDB	4.862486e-05
8,291	Adaptive Indexing over Encrypted Numeric Data	2016	SIGMOD	4.5392079e-05
9,769	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2815042e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,086	Pivot-based Metric Indexing	2017	VLDB	5.7036022e-05
1,290	Content-Based Image Indexing	1994	VLDB	0.00012774326
1,808	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010476269
10,754	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.1905499e-05
8,645	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4725847e-05
1,923	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010079134
9,769	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2815042e-05
7,790	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB	4.6458343e-05
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
574	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.0001987713