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: 8863
Venue: VLDB
Year: 2002
Pagerank: 4.5029015e-05
Overall Rank: 8,474 | 41.05%
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,742	AGILE: Adaptive Indexing for Context-Aware Information Filters	2005	SIGMOD	4.9432585e-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.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
252	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030632263
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021380733
1,335	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00012502131
2,053	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6728745e-05
2,835	Applying the Golden Rule of Sampling for Query Estimation	2001	SIGMOD	8.0448428e-05
6,076	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.223696e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,258	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB	4.3690661e-05
1,375	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00012303141
10,748	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.1945683e-05
2,363	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9580928e-05
6,201	Concurrency Control for Adaptive Indexing	2012	VLDB	5.1600319e-05
9,767	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2856106e-05
7,390	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	4.7431654e-05
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
8,655	Adaptive Hybrid Indexes	2022	SIGMOD	4.4739554e-05
6,708	Just-In-Time Data Structures	2015	CIDR	4.953106e-05