超快聚类算法，提速7倍且保持向量搜索质量
A Super Fast K-means for Indexing Vector Embeddings
- 通过动态剪枝无关维度，减少数据访问和计算开销
- 在现代CPU上比FAISS和Scikit-Learn快7倍，GPU上快4倍
- 引入召回率早停机制，加速收敛且不损失检索效果
我们提出SuperKMeans：一种针对高维向量嵌入聚类的k-means变体。其聚类速度在现代CPU上比FAISS和Scikit-Learn快达7倍，在GPU上比cuVS快4倍（图1），同时保持了用于向量相似性搜索的质心质量。加速源于通过可靠高效地剪枝无需参与向量-质心分配的维度，从而降低数据访问和计算开销。此外，我们提出了基于召回率的早停机制（Early Termination by Recall），在聚类质量不再提升时提前终止迭代，进一步缩短运行时间而不影响检索性能。代码已开源：https://github.com/cwida/SuperKMeans
原文摘要 · Abstract (English)
We present SuperKMeans: a k-means variant designed for clustering collections of high-dimensional vector embeddings. SuperKMeans' clustering is up to 7x faster than FAISS and Scikit-Learn on modern CPUs and up to 4x faster than cuVS on GPUs (Figure 1), while maintaining the quality of the resulting centroids for vector similarity search tasks. SuperKMeans acceleration comes from reducing data-access and compute overhead by reliably and efficiently pruning dimensions that are not needed to assign a vector to a centroid. Furthermore, we present Early Termination by Recall, a novel mechanism that early-terminates k-means when the quality of the centroids for retrieval tasks stops improving across iterations. In practice, this further reduces runtimes without compromising retrieval quality. We open-source our implementation at https://github.com/cwida/SuperKMeans
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。