BSP k-Means

We present a parallel k-Means clustering algorithm specifically designed to address large datasets and cluster counts. Our approach, BSP (binary space partitioning) k-Means, recursively partitions the input space optimally across the first principal component of the current subset of the data. From a single space partitioning, clusterings with arbitrary ?? can be found by a greedy tree search. Combining a reduction onto the first principal component and optimal binary clustering of 1D data is highly effective at reducing clustering costs. We attribute this to the close relationship between directional variance and the within-cluster sum of squares. We analyze our approach theoretically and, under an idealized population model, prove that the runtime is in O(n . max(d, lnn) · lnn) for a broad class of input distributions with high probability. We demonstrate that our algorithm consistently outperforms k-Means++ and performs similarly or better than other sophisticated algorithms in an evaluation with nine datasets and up to six cluster sizes. Our algorithm is parallelizable using common database operations such as Scan, Reduce, and Sort. We show that with our CUDA implementation, a significant speedup can be achieved. Additionally, our algorithm generates centers and datapoint assignments alike, removing the expensive cluster assignment step after initial seeding. Furthermore, our algorithm approximates k-Means accurately so that any additional use of Lloyd’s algorithm is optional and yields only incremental improvement.