Fast $k$-Means via Data-Aware Grouping and Gap-Optimized Lower Bound

Lloyd's algorithm for $k$-means clustering is a fundamental and widely used method for cluster discovery across various domains. However, its application to large-scale data is limited by the need to compute all point-to-centroid distances in each iteration. In this paper, we present a new bound-based implementation of Lloyd's algorithm that significantly improves computational efficiency through data-aware grouping and gap-optimized lower-bound computation. By partitioning the centroids based on the underlying data distribution, the data-aware grouping strategy produces tighter maintained lower bounds, thereby achieving a better balance between the costs of distance and non-distance computations. Furthermore, we introduce a mechanism that prioritizes the most informative dimensions to compute lower bounds, enabling the proposed implementation to skip unnecessary exact distance computations without compromising clustering accuracy. We prove that the proposed lower-bound computation is optimized with respect to data distribution under an orthogonal transformation. Experimental results confirm that the proposed implementation significantly outperforms the existing methods in efficiency.