Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability

Summary: A novel sort-based R-tree packing strategy achieves asymptotically optimal worst-case I/O for window queries while remaining efficient across data distributions. Its sorting-only structure enables strongly parallel bulk-loading with provable communication performance and scalable experiments. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11958
Venue: VLDB
Year: 2018
Pagerank: 5.6873519e-05
Overall Rank: 7,151 | 50.94%
DOI: 10.1145/3177732.3177738

Incoming Non-self Citations Over Time

Authors

1. Jianzhong Qi (University of Melbourne)
2. Yufei Tao (Chinese University of Hong Kong)
3. Yanchuan Chang (University of Melbourne)
4. Rui Zhang (University of Melbourne)

BibTeX Citation

@article{qi_vldb18,
        title = {{Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability}},
        author = {Qi, Jianzhong and Tao, Yufei and Chang, Yanchuan and Zhang, Rui},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {5},
        pages = {621--634},
        doi = {10.1145/3177732.3177738},
        url = {https://doi.org/10.1145/3177732.3177738},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,840	Effectively Learning Spatial Indices	2020	VLDB	9.6404567e-05
4,751	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	6.5241784e-05
6,537	Range Search over Encrypted Multi-Attribute Data	2023	VLDB	5.8478276e-05
9,974	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.1845938e-05
11,193	BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data	2024	SIGMOD	5.093636e-05
11,342	Efficient Cost Modeling of Space-filling Curves	2024	VLDB	5.093636e-05
11,664	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	5.093636e-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.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
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.0003221055
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
726	Client-Server Paradise	1994	VLDB	0.0001460632
1,207	Communication Steps for Parallel Query Processing	2013	PODS	0.00011663155
2,341	Parallel R-trees	1992	SIGMOD	8.7233426e-05
2,539	Minimal MapReduce Algorithms	2013	SIGMOD	8.4526595e-05
3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	7.2030591e-05
5,787	On the Optimality of Clustering Properties of Space Filling Curves	2012	PODS	6.088071e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,057	High-Concurrency Locking in R-Trees	1995	VLDB
2	3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS
3	4,569	Supporting Frequent Updates in R-Trees: A Bottom-Up Approach	2003	VLDB
4	9,234	On Optimal Node Splitting for R-trees	1998	VLDB
5	10,674	Parallel kd-tree with Batch Updates	2025	SIGMOD
6	2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD
7	5,304	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB
8	1,901	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB
9	3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD
10	2,341	Parallel R-trees	1992	SIGMOD