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: 8864
Venue: VLDB
Year: 2002
Pagerank: 4.4986491e-05
Overall Rank: 8,471 | 41.13%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yufei Tao
2. Dimitris Papadias

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,741	AGILE: Adaptive Indexing for Context-Aware Information Filters	2005	SIGMOD	4.9395718e-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.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
250	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030640525
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
369	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025502381
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021385343
1,331	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00012553948
2,056	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6692561e-05
2,840	Applying the Golden Rule of Sampling for Query Estimation	2001	SIGMOD	8.0417349e-05
6,073	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.2215154e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,365	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00012379754
9,168	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB	4.380727e-05
10,754	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.1905499e-05
6,201	Concurrency Control for Adaptive Indexing	2012	VLDB	5.1559919e-05
2,361	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9648608e-05
9,769	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2815042e-05
7,389	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	4.7386163e-05
8,764	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.4520434e-05
8,653	Adaptive Hybrid Indexes	2022	SIGMOD	4.4696663e-05
6,708	Just-In-Time Data Structures	2015	CIDR	4.948865e-05