Adaptive Indexing of Objects with Spatial Extent

Summary: Presents AIR-tree — the first adaptive index for non-point spatial objects that incrementally builds an in-memory R-tree over a static array using online node-creation/split heuristics. Outperforms point-focused adaptive indexing and static R-tree in cumulative time on early workloads. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13075
Venue: VLDB
Year: 2023
Pagerank: 4.2856106e-05
Overall Rank: 9,767 | 32.06%
DOI: 10.14778/3598581.3598596

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,283	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB	4.3631652e-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 15 of 15 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
408	Database Cracking	2007	CIDR	0.00023953844
1,478	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00011762542
1,607	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011162682
1,611	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00011147324
1,889	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00010200865
2,030	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7378136e-05
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
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
4,506	Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores	2012	VLDB	6.1319277e-05
4,780	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	5.9263494e-05
5,790	AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data	2015	VLDB	5.3269734e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,925	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010073407
6,500	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0381573e-05
3,275	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2897998e-05
9,095	AirIndex: Versatile Index Tuning Through Data and Storage	2023	SIGMOD	4.3975034e-05
8,474	Adaptive Index Structures	2002	VLDB	4.5029015e-05
2,586	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD	8.4928908e-05
9,283	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB	4.3631652e-05
2,541	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.5795657e-05
10,748	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.1945683e-05
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493