Why is kmeans using flat index faster than scikit learn

[sstone-codaio]

Hi, I benchmarked faiss (on CPU) and scikit learn for k means. The analysis is run on 1M vectors of size 33, assigning to 256 clusters, and faiss significantly outperforms scikit learn (>10x faster). I was not really expecting that, because I used the Flat index for centroids, and based on documentation "Flat indexes just encode the vectors into codes of a fixed size ... At search time, all the indexed vectors are decoded sequentially and compared to the query vectors.", it doesn't seem any performance gain should be expected. Is there any theoretical foundation as to why faiss runs a lot faster?

Happy to provide more details if need.

[alexanderguzhva]

1. It depends on the number of iterations that k-means uses. As far as I remember, Faiss uses 25 iterations by default.
2. By default, Faiss uses only a subset of samples for the clustering procedure, and it is 256 * nclusters, if I recall correctly. You can find the number that Faiss uses by turning on the verbose output.
3. Faiss uses Intel MKL and some optimized SIMD kernels.