K-means Split Revisited: Well-grounded Approach and Experimental Evaluation

Summary: Re-examines the k-means node-split for R-trees, uncovers theoretical flaws, and presents a well-grounded redesign. Empirical evaluation in PostgreSQL with a modern multidimensional benchmark demonstrates when the new split improves performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5223
Venue: SIGMOD
Year: 2016
Pagerank: 4.1945683e-05
Overall Rank: 11,852 | 17.55%
DOI: 10.1145/2882903.2914833

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Valentin Grigorev
2. George Chernishev

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-05
2,586	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD	8.4928908e-05
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
8,562	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD	4.4937074e-05
7,054	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	4.8496866e-05
9,207	Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree	2007	CIDR	4.3733038e-05
7,519	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB	4.7180617e-05
10,924	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1945683e-05
9,018	On Optimal Node Splitting for R-trees	1998	VLDB	4.4091374e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05