# Balanced k-means for Parallel Geometric Partitioning

arXiv: https://arxiv.org/abs/1805.01208 · HTML: https://mlsanity.com/paper/1805.01208/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2018.

## Built on by (most cited first, 2 of 2)

- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [Spatiotemporal Data Mining: A Survey](https://mlsanity.com/paper/2206.12753/) (2022)

## Abstract (arXiv)

Mesh partitioning is an indispensable tool for efficient parallel numerical simulations. Its goal is to minimize communication between the processes of a simulation while achieving load balance. Established graph-based partitioning tools yield a high solution quality; however, their scalability is limited. Geometric approaches usually scale better, but their solution quality may be unsatisfactory for `non-trivial' mesh topologies. In this paper, we present a scalable version of k-means that is adapted to yield balanced clusters. Balanced k-means constitutes the core of our new partitioning algorithm Geographer. Bootstrapping of initial centers is performed with space-filling curves, leading to fast convergence of the subsequent balanced k-means algorithm. Our experiments with up to 16384 MPI processes on numerous benchmark meshes show the following: (i) Geographer produces partitions with a lower communication volume than state-of-the-art geometric partitioners from the Zoltan package; (ii) Geographer scales well on large inputs; (iii) a Delaunay mesh with a few billion vertices and edges can be partitioned in a few seconds.