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: 13263
Venue: VLDB
Year: 2023
Pagerank: 5.2006273e-05
Overall Rank: 9,887 | 32.17%
DOI: 10.14778/3598581.3598596

Incoming Non-self Citations Over Time

Authors

1. Fatemeh Zardbani (Aarhus University)
2. Nikos Mamoulis (University of Ioannina)
3. Stratos Idreos (Harvard University)
4. Panagiotis Karras (Aarhus University)

BibTeX Citation

@article{zardbani_vldb23,
        title = {{Adaptive Indexing of Objects with Spatial Extent}},
        author = {Zardbani, Fatemeh and Mamoulis, Nikos and Idreos, Stratos and Karras, Panagiotis},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {9},
        pages = {2248--2260},
        doi = {10.14778/3598581.3598596},
        url = {https://doi.org/10.14778/3598581.3598596},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,898	Cracking Vector Search Indexes	2025	VLDB	5.3495662e-05
9,334	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB	5.2884486e-05
10,984	Benchmarking Adaptive Multidimensional Indices	2025	VLDB	5.093636e-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.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
259	Database Cracking	2007	CIDR	0.00023119313
873	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013481915
1,135	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00012032847
1,174	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011817414
1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011808761
1,679	Self-organizing Tuple Reconstruction in Column-stores	2009	SIGMOD	0.00010029136
1,811	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	9.698026e-05
1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.6928497e-05
2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.9083221e-05
3,830	Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores	2012	VLDB	7.0877801e-05
4,844	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	6.4826356e-05
5,395	AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data	2015	VLDB	6.2331619e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,778	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB
2	6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
3	3,217	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD
4	9,106	AirIndex: Versatile Index Tuning Through Data and Storage	2023	SIGMOD
5	8,689	Adaptive Index Structures	2002	VLDB
6	2,776	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD
7	9,334	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB
8	10,984	Benchmarking Adaptive Multidimensional Indices	2025	VLDB
9	2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
10	2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD