要旨: 私たちは、高次元ベクトル埋め込みの集合をクラスタリングするために設計された k-means の派生版、SuperKMeans を紹介します。
SuperKMeans のクラスタリングは、現代の CPU 上で FAISS および Scikit-Learn より最大で7倍速く、GPU 上では cuVS より最大で4倍速く（図1）、ベクトル類似検索タスクのための得られたセントロイドの品質を維持します。
SuperKMeans の加速は、ベクトルをセントロイドに割り当てるのに不要な次元を信頼性高く効率的に剪定することによって、データアクセスと計算のオーバーヘッドを削減することに起因します。
さらに、リコールによる早期終了という新機構を提示します。これは、検索タスクのセントロイドの品質が反復を重ねても改善されなくなったときに k-means を早期に終了させるものです。
実際には、検索品質を損なうことなく、実行時間をさらに短縮します。
実装をオープンソースとして公開しています https://github.com/cwida/SuperKMeans
ベクトル埋め込みのインデックス作成のための超高速K-means
arXiv cs.LG / 2026/3/23
📰 ニュースTools & Practical UsageModels & Research
要点
- SuperKMeans は高次元ベクトル埋め込みのクラスタリングを目的とした k-means の変種で、CPU 上の FAISS および Scikit-Learn より最大7倍速く、GPU 上の cuVS より最大4倍速く動作しつつ、検索タスクのための得られるセントロイドの品質を維持します。
- 高速化は、ベクトルをセントロイドに割り当てるのに不要な次元を剪定することから生じ、データアクセスと計算のオーバーヘッドを削減します。
- Recall による早期終了を導入し、検索タスクのセントロイドの品質が反復間で改善されなくなった場合に k-means を早期終了させ、検索品質を損なうことなく実行時間をさらに短縮します。
- 実装を https://github.com/cwida/SuperKMeans でオープンソース公開しています。
