On Optimal Node Splitting for R-trees

Summary: Polynomial-time optimal bipartition for R-tree node splits; valid for any objective depending only on bounding rectangles, O(n^d) (d>1). Experiments show 5-15% query-time gains over heuristics, implying near-optimality of current splits; with a global overflow-insertion strategy, gains up to 120% over the standard. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8691
Venue: VLDB
Year: 1998
Pagerank: 5.3017497e-05
Overall Rank: 9,234 | 36.65%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yván J. García R. (University of Denver)
2. Mario A. López (University of Denver)
3. Scott T. Leutenegger (University of Denver)

BibTeX Citation

@article{r_vldb98,
        title = {{On Optimal Node Splitting for R-trees}},
        author = {R., Yván J. García and López, Mario A. and Leutenegger, Scott T.},
        journal = {PVLDB},
        series = {{VLDB} '98},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.9083221e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.0003221055
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,373	A Model for the Prediction of R-tree Performance	1996	PODS
2	12,053	K-means Split Revisited: Well-grounded Approach and Experimental Evaluation	2016	SIGMOD
3	4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD
4	329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB
5	1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD
6	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
7	3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD
8	7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB
9	7,939	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB
10	2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD