Adaptive Indexing in High-Dimensional Metric Spaces

Summary: Introduces AV-tree, an adaptive high-dimensional metric index that reuses distances and query centers as vantage points, avoiding ineffective orthotope partitioning. It targets short-lived workloads, offering fast initial queries before converging to or surpassing MVP-tree performance. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hff020a8672c166a2
Venue: VLDB
Year: 2023
Pagerank: 5.1821189e-05
Overall Rank: 9,409 | 36.77%
DOI: 10.14778/3603581.3603592
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Konstantinos Lampropoulos (University of Ioannina)
2. Fatemeh Zardbani (Aarhus University)
3. Nikos Mamoulis (University of Ioannina)
4. Panagiotis Karras (Aarhus University)

BibTeX Citation

@article{lampropoulos_vldb23,
        title = {{Adaptive Indexing in High-Dimensional Metric Spaces}},
        author = {Lampropoulos, Konstantinos and Zardbani, Fatemeh and Mamoulis, Nikos and Karras, Panagiotis},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {10},
        pages = {2525--2537},
        doi = {10.14778/3603581.3603592},
        url = {https://doi.org/10.14778/3603581.3603592},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,435	Cracking Vector Search Indexes	2025	VLDB	5.5266018e-05
7,594	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.4865404e-05
11,371	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.9769913e-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.0019923528
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.0005758001
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040363819
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037145866
197	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025572265
252	Database Cracking	2007	CIDR	0.00023101361
1,693	Self-organizing Tuple Reconstruction in Column-stores	2009	SIGMOD	9.8522869e-05
1,837	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	9.5315292e-05
2,384	The Uncracked Pieces in Database Cracking	2014	VLDB	8.5401256e-05
2,498	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	8.3800917e-05
3,606	Updating a Cracked Database	2007	SIGMOD	7.1653182e-05
3,879	Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores	2012	VLDB	6.9481594e-05
4,642	Pivot-based Metric Indexing	2017	VLDB	6.4874232e-05
5,968	k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation	2016	VLDB	5.9297183e-05
6,751	Progressive Indexes: Indexing for Interactive Data Analysis	2019	VLDB	5.6880934e-05
6,918	Adaptive Indexing over Encrypted Numeric Data	2016	SIGMOD	5.6435526e-05
10,053	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	5.0875233e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,642	Pivot-based Metric Indexing	2017	VLDB
2	1,406	Content-Based Image Indexing	1994	VLDB
3	2,077	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS
4	11,371	Benchmarking Adaptive Multidimensional Indices	2025	VLDB
5	8,827	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD
6	1,793	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB
7	10,053	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
8	7,860	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB
9	45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB
10	597	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD