Re:E-means: 10x faster k-means at equal loss
by swann_bessa on Tuesday November 10, 2026 @09:58AM
(#50441319)
Thanks for your kind responses.
I'd be very interested if they have a reference. If you feel like it, you can always send me an e-mail at [email protected] with the references. I'll add them to my benchmarks.
The fewer centroids case is super interesting. Because we found in our experiments that basically if your n/k ratio (n is the dataset size, k the number of clusters) is high, running the clustering as is on your n points is a waste of resource. You should subsample your dataset such that there is about 250 points per cluster and you will get very similar loss at a fraction of the compute. This is why faiss k-means, by default, subsamples datasets to 256 points per cluster if n/k > 256.
So I fully agree with your computational remarks, but I think it's a case that should never happen in practice because subsampling your dataset is the solution in those cases.
I'd be very interested if they have a reference. If you feel like it, you can always send me an e-mail at [email protected] with the references. I'll add them to my benchmarks.
The fewer centroids case is super interesting. Because we found in our experiments that basically if your n/k ratio (n is the dataset size, k the number of clusters) is high, running the clustering as is on your n points is a waste of resource. You should subsample your dataset such that there is about 250 points per cluster and you will get very similar loss at a fraction of the compute. This is why faiss k-means, by default, subsamples datasets to 256 points per cluster if n/k > 256. So I fully agree with your computational remarks, but I think it's a case that should never happen in practice because subsampling your dataset is the solution in those cases.