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: 13076
Venue: VLDB
Year: 2023
Pagerank: 4.2815042e-05
Overall Rank: 9,769 | 32.11%
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,288	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB	4.3589837e-05
10,718	Cracking Vector Search Indexes	2025	VLDB	4.1905499e-05
10,754	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.1905499e-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.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
407	Database Cracking	2007	CIDR	0.00023941779
1,464	Learning Multi-dimensional Indexes	2020	SIGMOD	0.0001184772
1,608	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00011169837
1,610	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011155922
1,887	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00010201938
2,033	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7315522e-05
2,231	Self-organizing Tuple Reconstruction in Column-stores	2009	SIGMOD	9.2367968e-05
2,361	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9648608e-05
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
4,507	Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores	2012	VLDB	6.1271582e-05
4,778	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	5.9259497e-05
5,800	AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data	2015	VLDB	5.3218628e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,923	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010079134
6,496	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0327729e-05
3,278	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2858181e-05
9,093	AirIndex: Versatile Index Tuning Through Data and Storage	2023	SIGMOD	4.3932886e-05
8,471	Adaptive Index Structures	2002	VLDB	4.4986491e-05
2,592	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD	8.4841264e-05
9,288	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB	4.3589837e-05
10,754	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	4.1905499e-05
2,558	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.5441554e-05
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032118946