A Super Fast K-means for Indexing Vector Embeddings

• URL: http://arxiv.org/abs/2603.20009v1
• Date: Fri, 20 Mar 2026 14:52:38 GMT
• Title: A Super Fast K-means for Indexing Vector Embeddings
• Abstract summary: SuperKMeans is a k-means variant designed for clustering high-dimensional vector embeddings.<n>SuperKMeans clustering is up to 7x faster than FAISS and Scikit-Learn on modern CPUs.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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

Related papers

• Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings [0.0]
  In this study, we revisit three widely used techniques in vector search and utilize them to optimize vector embedding indexing through clustering.<n>We propose an indexing pipeline in which these techniques are applied before clustering, and we focus on how they affect storage footprint, clustering time, and the quality of the resulting centroids for vector search tasks.
  arXiv  Detail & Related papers  (2026-07-30T12:59:55Z)
• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  Single-stage Sparse Retrieval (SSR) is a paradigm shift that replaces expensive clustering with efficient sparse coding.<n>It reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance.
  arXiv  Detail & Related papers  (2026-05-28T15:53:34Z)
• Efficient Multivector Retrieval with Token-Aware Clustering and Hierarchical Indexing [11.098422338598454]
  TACHIOM is a multivector retrieval system that exploits token-level structure to significantly accelerate both clustering and retrieval.<n>By accounting for tokens' distribution during centroid allocation, TACHIOM easily scales to millions of centroids, enabling highly accurate document scoring using only centroids.
  arXiv  Detail & Related papers  (2026-04-30T17:30:15Z)
• Analysis of Nystrom method with sequential ridge leverage scores [69.32538992633842]
  Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix K_t.<n>Recent works show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for the approximation.<n>We introduce the INK-ESTIMATE algorithm, that incrementally computes the RLSs estimates.
  arXiv  Detail & Related papers  (2026-04-22T00:49:25Z)
• Multi-Vector Index Compression in Any Modality [73.7330345057813]
  Late interaction has emerged as a dominant paradigm for information retrieval in text, images, visual documents, and videos.<n>We introduce four approaches for index compression: sequence resizing, memory tokens, hierarchical pooling, and a novel attention-guided clustering (AGC)<n>AGC uses an attention-guided mechanism to identify the most semantically salient regions of a document as cluster centroids and to weight token aggregation.
  arXiv  Detail & Related papers  (2026-02-24T18:57:33Z)
• Communication-Avoiding Linear Algebraic Kernel K-Means on GPUs [1.0017970035130424]
  We present a suite of distributed-memory parallel algorithms for large-scale Kernel K-means clustering.<n>Our approach maps the most computationally expensive components of Kernel K-means onto communication-efficient distributed linear algebra primitives.<n>Our 1.5D algorithm consistently achieves the highest performance, enabling Kernel K-means to scale to data one to two orders of magnitude larger than previously practical.
  arXiv  Detail & Related papers  (2026-01-23T19:25:10Z)
• Rock the KASBA: Blazingly Fast and Accurate Time Series Clustering [0.6215404942415159]
  We present a new time series clustering (TSCL) algorithm, the $k$-means (K) accelerated (A) subgradient (S) Barycentre (B) Average (A)<n> KASBA is a $k$-means clustering algorithm that uses the Move-Split-Merge (MSM) elastic distance at all stages of clustering, applies a randomised subgradient descent to find barycentre centroids, links each stage of clustering to accelerate convergence and exploits the metric property of MSM distance to avoid a large proportion of distance calculations.<n>It is a versatile and scalable clusterer designed for
  arXiv  Detail & Related papers  (2024-11-26T19:26:17Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  Fuzzy K-Means clustering is a critical technique in unsupervised data analysis. This paper proposes a novel Fuzzy textitK-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
  arXiv  Detail & Related papers  (2024-04-07T12:25:03Z)
• K-Splits: Improved K-Means Clustering Algorithm to Automatically Detect the Number of Clusters [0.12313056815753944]
  This paper introduces k-splits, an improved hierarchical algorithm based on k-means to cluster data without prior knowledge of the number of clusters. Accuracy and speed are two main advantages of the proposed method.
  arXiv  Detail & Related papers  (2021-10-09T23:02:57Z)
• Exact Acceleration of K-Means++ and K-Means$\|$ [22.66983713481359]
  K-Means++ and K-Means$|$ have become de facto tools for selecting the initial seeds of K-means. We develop specialized triangle inequality pruning strategies and a dynamic priority queue to show the first acceleration of K-Means++ and K-Means$|$.
  arXiv  Detail & Related papers  (2021-05-06T20:22:55Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  In this work we consider the problem of center-based clustering of trajectories. We propose the usage of a continuous version of DTW as distance measure, which we call continuous dynamic time warping (CDTW) We show a practical way to compute a center from a set of trajectories and subsequently iteratively improve it.
  arXiv  Detail & Related papers  (2020-12-01T13:17:27Z)
• SimpleMKKM: Simple Multiple Kernel K-means [49.500663154085586]
  We propose a simple yet effective multiple kernel clustering algorithm, termed simple multiple kernel k-means (SimpleMKKM) Our criterion is given by an intractable minimization-maximization problem in the kernel coefficient and clustering partition matrix. We theoretically analyze the performance of SimpleMKKM in terms of its clustering generalization error.
  arXiv  Detail & Related papers  (2020-05-11T10:06:40Z)
• Ball k-means [53.89505717006118]
  The Ball k-means algorithm uses a ball to describe a cluster, focusing on reducing the point-centroid distance computation. The fast speed, no extra parameters and simple design of the Ball k-means make it an all-around replacement of the naive k-means algorithm.
  arXiv  Detail & Related papers  (2020-05-02T10:39:26Z)
• On Coresets for Support Vector Machines [61.928187390362176]
  A coreset is a small, representative subset of the original data points. We show that our algorithm can be used to extend the applicability of any off-the-shelf SVM solver to streaming, distributed, and dynamic data settings.
  arXiv  Detail & Related papers  (2020-02-15T23:25:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.