TL;DR: We fused SuperKMeans and e-means, resulting in 3× faster clustering of high-dimensional vectors without quality trade-offs. Available now at https://github.com/cwida/SuperKMeans.
Recently, there has been a lot of buzz around clustering of vector embeddings: EVōC, SuperKMeans, QGKmeans, and just last week, e-means, o-means, and s-means. Among these, e-means is a big deal: it promises the same quality as Lloyd’s with only 2 epochs. Why is this a big deal for vector search?
Well, clustering is a key building block for large-scale vector indexes (e.g., IVF, ScANN), which is precisely the bottleneck that users have to wait on before issuing similarity search queries.
A year ago, we released SuperKMeans. SuperKMeans accelerates Lloyd’s k-means by 2—10× by avoiding scanning vector dimensions while clustering, without trade-offs in clustering quality. SuperKMeans has been rapidly adopted by industry (ParadeDB, Zilliz, FAISS), showing how timely it is to improve clustering performance for high-dimensional vectors. However, e-means is also exciting because it tackles effort by running fewer epochs. Traditionally, clustering for vector embeddings is standardized to 10 epochs. e-means promises the same (or better) clustering quality with…