Adaptive Index Structures

Summary: A general framework for adaptive indexes that minimizes total query cost by allowing index nodes to hold a variable number of disk pages and reconfiguring dynamically based on data and query characteristics. Adaptive B- and R-trees outperform conventional variants with modest update overhead. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9054
Venue: VLDB
Year: 2002
Pagerank: 5.3843737e-05
Overall Rank: 8,689 | 40.39%
DOI: 10.1016/B978-155860869-6/50044-5

Incoming Non-self Citations Over Time

Authors

1. Yufei Tao (Hong Kong University of Science and Technology)
2. Dimitris Papadias (Hong Kong University of Science and Technology)

BibTeX Citation

@article{tao_vldb02,
        title = {{Adaptive Index Structures}},
        author = {Tao, Yufei and Papadias, Dimitris},
        journal = {PVLDB},
        series = {{VLDB} '02},
        pages = {13--24},
        doi = {10.1016/B978-155860869-6/50044-5},
        url = {https://doi.org/10.1016/B978-155860869-6/50044-5},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,647	AGILE: Adaptive Indexing for Context-Aware Information Filters	2005	SIGMOD	5.8147547e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
222	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00024193708
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
1,166	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011850439
2,127	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.127762e-05
2,493	Applying the Golden Rule of Sampling for Query Estimation	2001	SIGMOD	8.5070756e-05
6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.9806097e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	790	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD
2	9,324	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB
3	10,984	Benchmarking Adaptive Multidimensional Indices	2025	VLDB
4	1,811	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB
5	5,903	Concurrency Control for Adaptive Indexing	2012	VLDB
6	9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
7	6,687	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD
8	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
9	7,012	Adaptive Hybrid Indexes	2022	SIGMOD
10	6,429	Just-In-Time Data Structures	2015	CIDR