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: 5285
Venue: SIGMOD
Year: 2016
Pagerank: 5.093636e-05
Overall Rank: 12,053 | 17.31%
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 (Saint Petersburg State University)
2. George Chernishev (Saint Petersburg State University)

BibTeX Citation

@inproceedings{grigorev_sigmod16,
        title = {{K-means Split Revisited: Well-grounded Approach and Experimental Evaluation}},
        author = {Grigorev, Valentin and Chernishev, George},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2914833},
        url = {https://dl.acm.org/doi/10.1145/2882903.2914833},
        year = {2016}
}

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.0020210012
2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.9083221e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,776	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD
2	85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB
3	8,765	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD
4	7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB
5	9,365	Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree	2007	CIDR
6	7,939	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB
7	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS
8	10,153	Faster Relational Algorithms Using Geometric Data Structures	2026	PODS
9	9,234	On Optimal Node Splitting for R-trees	1998	VLDB
10	2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD