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: 11771
Venue: VLDB
Year: 2018
Pagerank: 4.8471584e-05
Overall Rank: 7,046 | 51.04%
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,676	Effectively Learning Spatial Indices	2020	VLDB	8.326321e-05
5,463	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	5.4920768e-05
6,395	Range Search over Encrypted Multi-Attribute Data	2023	VLDB	5.0766624e-05
9,826	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	4.2710095e-05
10,983	BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data	2024	SIGMOD	4.1905499e-05
11,139	Efficient Cost Modeling of Space-filling Curves	2024	VLDB	4.1905499e-05
11,469	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1905499e-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.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
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065500256
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
217	A Class of Data Structures for Associative Searching	1984	PODS	0.00033533621
356	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026091196
766	Client-Server Paradise	1994	VLDB	0.0001690298
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832
2,245	Parallel R-trees	1992	SIGMOD	9.2048202e-05
2,714	Minimal MapReduce Algorithms	2013	SIGMOD	8.2426646e-05
4,026	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5166769e-05
5,972	On the Optimality of Clustering Properties of Space Filling Curves	2012	PODS	5.2462762e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,042	High-Concurrency Locking in R-Trees	1995	VLDB	7.6669657e-05
4,026	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS	6.5166769e-05
4,683	Supporting Frequent Updates in R-Trees: A Bottom-Up Approach	2003	VLDB	5.9940496e-05
9,021	On Optimal Node Splitting for R-trees	1998	VLDB	4.4049428e-05
10,398	Parallel kd-tree with Batch Updates	2025	SIGMOD	4.1905499e-05
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
5,294	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5777973e-05
2,139	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4618572e-05
3,653	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	6.8725114e-05
2,245	Parallel R-trees	1992	SIGMOD	9.2048202e-05