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: 13099
Venue: VLDB
Year: 2023
Pagerank: 4.3631652e-05
Overall Rank: 9,283 | 35.43%
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.1945683e-05
10,711	Cracking Vector Search Indexes	2025	VLDB	4.1945683e-05
10,748	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.1945683e-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.0032169493
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030040036
408	Database Cracking	2007	CIDR	0.00023953844
2,229	Self-organizing Tuple Reconstruction in Column-stores	2009	SIGMOD	9.2350274e-05
2,363	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9580928e-05
2,987	The Uncracked Pieces in Database Cracking	2014	VLDB	7.7787088e-05
3,772	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	6.7761705e-05
3,896	Updating a Cracked Database	2007	SIGMOD	6.6575888e-05
4,506	Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores	2012	VLDB	6.1319277e-05
4,985	Pivot-based Metric Indexing	2017	VLDB	5.7856648e-05
6,200	k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation	2016	VLDB	5.1602201e-05
7,001	Progressive Indexes: Indexing for Interactive Data Analysis	2019	VLDB	4.8671553e-05
8,297	Adaptive Indexing over Encrypted Numeric Data	2016	SIGMOD	4.5435639e-05
9,767	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2856106e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,985	Pivot-based Metric Indexing	2017	VLDB	5.7856648e-05
1,293	Content-Based Image Indexing	1994	VLDB	0.00012783639
1,811	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010467197
10,748	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.1945683e-05
8,647	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4768766e-05
1,925	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010073407
9,767	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2856106e-05
7,791	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB	4.6502309e-05
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723