Introduction
The scalability of $k$-means clustering is a critical challenge in modern data science, particularly for high-dimensional datasets common in image retrieval. The standard Lloyd’s algorithm requires an assignment step where each of $n$ data points is compared against $k$ cluster centers, resulting in $O(nk)$ complexity per iteration. For datasets with millions of points and clusters, this becomes a prohibitive computational bottleneck.
While approximate methods like Hierarchical $K$-Means (HKM) and forest-based Approximate $K$-Means (AKM) have been proposed, they often suffer from accuracy loss or high maintenance overhead. This paper introduces Cluster Closures, a method that exploits the spatial stability of data points to achieve nearly $O(n)$ complexity.
The Active Point Hypothesis
A key insight of this work is that most data points do not change their cluster assignments between iterations. The "active" points—those that do switch—are typically found near the boundaries between clusters.
As shown in the figure above, points with a small distance ratio (the ratio of distances to the nearest and second-nearest centers) are much more likely to be active. By focusing computational effort on these boundary regions, the algorithm can bypass exhaustive searches for the majority of the dataset.
Methodology: Cluster Closures
The proposed algorithm, Cluster Closure, operates in three main phases:
1. Pre-processing and Neighborhood Indexing
Unlike previous methods that re-index moving cluster centers, Cluster Closure indexes the static data points once. Using multiple Random Partition (RP) trees, the algorithm groups neighboring points into leaf nodes. This neighborhood information remains valid throughout the clustering process.
2. Defining Cluster Closures
A "cluster closure" $\bar{G}$ is defined as the union of the neighborhoods $N_x$ of all points $x$ currently assigned to a cluster $G$. This creates an expanded region that encompasses the cluster and its immediate surroundings.
3. Fast Assignment
During the assignment step, a point $x$ is only compared against cluster centers whose closures contain $x$. Since any given point typically falls within only a few cluster closures, the number of candidate centers is reduced to a small constant, effectively decoupling the complexity from $k$.
Experimental Evaluation
The authors evaluated Cluster Closure on several large-scale computer vision datasets, including 1M SIFT features and 1M GIST features (Tiny Images).
Performance and Scalability
On a dataset of 1M GIST features with 10K clusters, the algorithm achieved a 2.5x speedup over state-of-the-art AKM and HKM implementations. Furthermore, the assignment step demonstrated nearly linear parallel speedup on multi-core systems.
Clustering Quality
In image retrieval benchmarks (Oxford 5K and Ukbench 10K), visual codebooks generated via Cluster Closures outperformed those from competing methods. For instance, a 750K-word codebook from this method yielded better retrieval accuracy than a 1M-word codebook from standard AKM, indicating superior cluster quality.
Conclusion
Cluster Closures offer a powerful alternative for large-scale $k$-means by shifting the focus from dynamic center indexing to static data indexing. By targeting the boundary regions where cluster assignments are most likely to change, the method achieves significant speedups without sacrificing accuracy. Future work may address memory overhead for massive datasets and explore the application of this technique to non-visual high-dimensional domains.
Summary updated