Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability

Summary: Novel R-tree packing strategy yielding asymptotically optimal I/O for window queries in worst-case distributions. Simple to parallelize by sorting; provides a parallel bulk-loading algorithm with MPC analysis and results on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11770
Venue: VLDB
Year: 2018
Pagerank: 4.8496866e-05
Overall Rank: 7,054 | 50.93%
DOI: 10.1145/3177732.3177738

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,678	Effectively Learning Spatial Indices	2020	VLDB	8.3252088e-05
5,572	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	5.4277273e-05
6,424	Range Search over Encrypted Multi-Attribute Data	2023	VLDB	5.0670573e-05
9,827	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	4.2751057e-05
10,980	BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data	2024	SIGMOD	4.1945683e-05
11,136	Efficient Cost Modeling of Space-filling Curves	2024	VLDB	4.1945683e-05
11,466	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1945683e-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
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065631356
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
216	A Class of Data Structures for Associative Searching	1984	PODS	0.00033542705
354	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026137988
769	Client-Server Paradise	1994	VLDB	0.00016918508
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
2,246	Parallel R-trees	1992	SIGMOD	9.2075292e-05
2,674	Minimal MapReduce Algorithms	2013	SIGMOD	8.3328645e-05
4,021	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5225987e-05
5,990	On the Optimality of Clustering Properties of Space Filling Curves	2012	PODS	5.2424347e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,039	High-Concurrency Locking in R-Trees	1995	VLDB	7.6708607e-05
4,021	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5225987e-05
4,692	Supporting Frequent Updates in R-Trees: A Bottom-Up Approach	2003	VLDB	5.9958252e-05
9,018	On Optimal Node Splitting for R-trees	1998	VLDB	4.4091374e-05
10,387	Parallel kd-tree with Batch Updates	2025	SIGMOD	4.1945683e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
5,328	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5665496e-05
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-05
3,650	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	6.8783391e-05
2,246	Parallel R-trees	1992	SIGMOD	9.2075292e-05