CS Paper Radar

HDLouvain: High-Throughput Incremental Clustering for Hyperdimensional Data

Beenish Gul, Mahbod Afarin, Farhat Ahmed, Sumukh Pinge, Tsung-Han Lu, Tajana Rosing, Kevin Skadron

cs.AR ·submitted 2026-10-22 03:58 UTC · v1
benchmark

Abstract

Modern shotgun proteomics generates tens of thousands of tandem mass spectra per hour, producing hundreds of gigabytes of data that strain conventional clustering pipelines. DBSCAN and hierarchical agglomerative clustering (HAC) offer flexible similarity search, but DBSCAN is unstable across varying data densities, HAC costs $O(n^2)$, and both yield poor cluster quality. Graph-based methods such as Louvain produce high-quality clusters but scale poorly on streaming data. We observe that Louvain's poor scalability can be resolved without sacrificing its quality, and present HDLouvain, which combines Louvain community detection with the bit-parallel similarity computation of hyperdimensional computing (HDC). HDLouvain partitions a bootstrap fraction of the stream into precursor-mass buckets, applies Louvain to each bucket's kNN similarity graph, and condenses each community into a single binary hypervector by bitwise-majority bundling rather than iterative centroid recomputation. New spectra are assigned by a GPU-accelerated Hamming distance lookup against representatives in their mass bucket, or seed a new cluster when no match meets a similarity threshold $τ$, so the partition grows incrementally without full re-clustering. On five PRIDE datasets (0.99M to 21.13M spectra), sweeping the bootstrap fraction $α$ from 0.2 to 0.9 exposes an explicit, monotonic throughput-fidelity trade-off. On PXD003258, speedup ranges from 4.5x at $α=0.3$ to 1.65x at $α=0.7$. Modularity rises from 0.75-0.76 at $α=0.2$ to 0.95-0.97 at $α=0.9$, never more than 8% below full static recomputation. The Louvain stage achieves 0.86-0.93 normalized mutual information (NMI) on LFR benchmark networks with 30k to 2M nodes, whereas DBSCAN and HAC degrade to 0.57.

Closest papers

Nearest neighbours by meaning across the whole index.

COMPASS: Steering Distributed Vector Search with Scientific Knowledge Graphs

cs.DB cs.DC ·2026-09-11 ·Song Young Oh, Amal Gueroudji, Seth Ockerman, Rob Latham, Orcun Yildiz +3 more
similarity 0.60
Abstract

Vector databases use hashing to partition data across "shards," logical units for distributed execution. This placement, however, destroys semantic locality, forcing each query into scatter-gather limited by the slowest shard. Vector-space clustering can help, but scientific evidence is often connected by factual relations that do not align with embedding distance. We present COMPASS, a framework that uses a knowledge graph (KG) to determine data placement and query-time shard selection. COMPASS detects communities, splits oversized communities, inserts embeddings by subject entity, and routes queries to a small set of shards. Across four biomedical KGs, our method searches only 13-18% of the corpus while preserving broadcast recall and recovering up to 2.6x more multi-hop evidence than an embedding-based baseline. On 15 HPC nodes, COMPASS sustains 7.9x higher throughput with lower tail latency than hash-based broadcast. These results show that KG structure provides a compact complement to embedding geometry for scalable vector search.

0.16

Accelerating FastDEC Clustering Algorithm with GPUs

cs.LG ·2026-11-02 ·Mi Li, Eibe Frank, Bernhard Pfahringer
hot direction similarity 0.60
Abstract · submitted to DMKD

Fast Dominance Estimation Clustering (FastDEC) is an efficient variant of Density Peak Clustering (DPC) that achieves high clustering quality through dominance-based density estimation, but remains constrained by the computational cost of exact k-nearest-neighbor (k-NN) construction and dominance component (DC) processing. We present SymWarp-FastDEC, a GPU-accelerated implementation of FastDEC. At its core is SymTrikNN, an exact self-k-NN kernel that exploits search symmetry using upper-triangular traversal and warp-cooperative top-k selection. We also introduce WP-DC, a warp-parallel DC reduction algorithm designed for modern GPUs. Combined with memory-adaptive execution planning and stream scheduling, WP-DC eliminates DC reduction as a runtime bottleneck. Experiments on synthetic and real-world datasets show that SymWarp-FastDEC produces clustering outputs identical to the original FastDEC on all evaluated equivalence benchmarks. Compared with a FastDEC variant using FAISS GpuIndexFlatL2 for exact k-NN search, our approach achieves approximately 1.7x to 4.9x higher end-to-end performance, with the advantage generally increasing with dimensionality. Compared with the original single-threaded Python FastDEC implementation, speedups reach approximately 2.5 x 10^4 in a very high-dimensional case where its k-d-tree-based search degrades; this extreme result is not representative of typical acceleration.

0.33

GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization

cs.LG cs.ARcs.PF ·2026-09-28 ·Peng Xu, Nihar Koganti, Volodymyr Kindratenko, Xiaohui Chen
similarity 0.58
Abstract

Memory-efficient scaling on clustering problems without sacrificing statistical accuracy is of central interest for large-scale data analysis and machine learning problems. Nonnegative low-rank (NLR) matrix factorization for $K$-means is a scalable clustering method, which connects to semidefinite relaxations with optimal average-case exact recovery guarantees. However, a direct GPU implementation of NLR requires multiple large factor-sized buffers and substantial data movements that are essentially memory-bound. In this paper, we introduce GEM-KMeans, a spectrally normalized yet mathematically equivalent NLR formulation that fuses the gradient update, nonnegative projection, and sufficient statistics for normalization and iterate movement into a matrix-multiplication epilogue. Instead of retaining three massive factor-sized arrays, our IO-aware GPU implementation materializes only one single factor with small tile-reduction arrays as additional storage in the High Bandwidth Memory (HBM). We derive explicit memory costs and spectrally normalized smoothness bounds for optimizing the clustering objective function. Accurate clustering is demonstrated at massive scales on synthetic and real datasets, where performance gains of GEM-KMeans over existing GPU-accelerated Lloyd's algorithms involve data-dependent runtime tradeoffs.

0.28

Turbocharging PiPNN for Proximity and $k$-NN Graph Building

cs.DB cs.IR ·2026-11-03 ·Tobias Rubel, Richard Wen, Guy Blelloch, Laxman Dhulipala, Lars Gottesbüren +2 more
similarity 0.58
Abstract

Graph-based Approximate Nearest Neighbor Search (ANNS) indexes such as HNSW and Vamana deliver state-of-the-art query performance at the cost of large indexing times. The recently introduced PiPNN method drastically accelerated index construction by way of a partitioning-based algorithm leveraging dense matrix multiplication and top-$K$ aggregation kernels. In this paper, we unlock the full potential of PiPNN's hardware-friendly algorithm design. We introduce PiPNN II, which optimizes multiple steps of the PiPNN recipe, giving up to $8\times$ speedups for graph-based ANNS index construction. In addition, we present GPiPNN, a GPU implementation which builds comparable ANNS indices up to $43.7\times$ faster than Jasper and up to $50\times$ faster than CAGRA. We also extend PiPNN II and GPiPNN to compute high-quality $k$-NN graphs directly, which unlocks massive speedups over methods used in many existing systems for clustering, anomaly detection, and more. For 10-NN graph building at $90\%$ recall, we obtain up to a $13\times$ speedup on CPUs and $6.6\times$ on GPUs as compared to the prior best methods. PiPNN II can build a billion-scale 10-NN graph in under 16 minutes. Common to both PiPNN II and GPiPNN is the use of quantization to reduce memory traffic and leverage fast low-precision matrix operations. Top-$K$ emerges as a new bottleneck, which we optimize with specialized code for specific $K$, and by fusing with the matrix kernel to avoid materializing the distance matrix to memory. On CPUs, we demonstrate further performance improvements by leveraging our matrix kernels in the RobustPrune procedure proposed in Vamana and used in PiPNN. On GPUs, we flatten recursive partitioning into segmented batches, use one fused top-$K$ abstraction for partitioning and leaf scoring, and prune with already-witnessed direct edges rather than new candidate-to-candidate scoring passes.

0.49

Fast and Actionable Classification of HPC I/O Time Series

cs.DC ·2026-11-06 ·Maxime Gonthier, Luan Teylo, Francesco Antici, Mihail Popov, Francieli Boito
similarity 0.57
Abstract

Input/output (I/O) is a major bottleneck for highperformance computing (HPC) performance. One of the challenges is the contention between jobs when sharing the parallel file system. However, tackling this issue depends on knowing the temporal behavior of jobs. In this paper, we propose a clusteringbased approach to characterize jobs' temporal I/O behavior. We propose SAGE, a lightweight method that cuts I/O traces into short windows and learns an alphabet from them. The trace then becomes a sequence of symbols, which we call ''genome'', and we use clustering to separate them into classes. We evaluate SAGE and its two-stage variant SAGE-2 on 819,771 real traces from 2 HPC systems. We compare them against other techniques from the state of the art on three metrics, including one we propose. Compared to K-shape, the best baseline available, SAGE-2 lowers the median intra-cluster metrics by 9.1% on average, and achieves this in 2 minutes of clustering time versus 3.8 hours, a 109x speedup. More importantly, clusters created by SAGE and SAGE-2 carry enough information to act on: we evaluate the use of the cluster centroids for I/O scheduling, and show that our approach can decrease I/O stretch by up to 24% compared to the state of the art (round-robin placement).

0.27

NeuRoute: Logit-Guided Neural Routing for Billion-Scale Vector Search with Sub-Hour Index Construction

cs.DB cs.IRcs.LG ·2026-08-15 ·Xingqiao Wang, Zi Wang, Xiaowei Xu
code/data similarity 0.55
Abstract · 34 pages, 9 figures

Building approximate nearest neighbor (ANN) indexes at billion scale is often dominated by expensive global clustering or graph construction, making time-to-index a first-order systems concern. We present NeuRoute, a learned hashing index that turns short binary codes into an effective routing primitive for large-scale vector search. NeuRoute trains a lightweight neural network encoder with a selective similarity-preserving objective to produce well-balanced binary addresses. During construction, NeuRoute organizes vectors into buckets by their codes and performs bucket-local clustering in the encoder's low-dimensional space to form centroids. At query time, NeuRoute exploits the encoder logits as an uncertainty signal: it uses deviation-to-threshold scores to prioritize uncertain-bit perturbations for query-adaptive multi-bucket probing, scores bucket-local centroids by their distances to the query to form a compact candidate cluster set, and applies centroid-stage gating with heap-quality-driven early stopping to prune low-value clusters before exact refinement. On billion-scale benchmarks, NeuRoute achieves strong accuracy-throughput trade-offs with fast index construction: on BigANN-1B it reaches $90.3\%$ Recall@10 at 2,414 QPS and is $1.7\times$ faster than OPQ+IVF-PQ (refine) at comparable accuracy, while completing end-to-end training+construction in under an hour on both BigANN-1B and Deep1B-1B. These results show that logit-guided neural routing can make hashing competitive as a lightweight ANN indexing framework at billion scale. Source code and artifacts are available at https://github.com/XingqiaoWang/NeuRoute.

0.30

SIMQ: A Single Graph-based Index for Multi-Vector Query

cs.IR cs.DB ·2026-11-17 ·Yifan Lu, Jiabao Jin, Xiaoyao Zhong, Peng Cheng, Xiangyu Wang +5 more
publishedcode/data similarity 0.55
Abstract · under ICDE 2027 review, 13 pages

Multi-vector retrieval models such as ColBERT achieve state-of-the-art effectiveness by representing documents as sets of token-level vectors and scoring via MaxSim, but their high computational cost limits scalability to large corpora. Existing approximate methods face fundamental bottlenecks: centroid interaction matrix approaches require computing a full matrix at every query and rely on GPU-accelerated clustering, while data-oblivious compression methods yield unstable recall that requires repeated compensation. We propose SIMQ (Single graph Index for Multi-vector Query), a framework that bridges single-vector graph indices and multi-vector retrieval through data-aware sampling-based clustering and per-token graph navigation, simultaneously bypassing all aforementioned bottlenecks. SIMQ organizes all token vectors into fine-grained clusters via data-aware sampling, builds a single graph index over cluster centroids independently of PLAID's residual representation, and approximates the MaxSim score through per-token graph search without materializing any interaction matrix or relying on GPU acceleration. We provide theoretical analysis showing that, under a manifold assumption and successful cell retrieval, data-aware partitioning has a smaller expected approximation error than a data-oblivious partition. Building on this foundation, SIMQ+ further introduces count-based scoring and a dynamic candidate set to improve robustness across varying query conditions. Experiments on five benchmarks compare recall, throughput, and construction time against several baselines, primarily on CPU; large-scale PLAID k-means centroids are built on a separate GPU machine. SIMQ has been integrated into VSAG, an Ant Group's open-source vector search library.

0.32

Fast and Memory-Light Evaluation of Density-Based Clusterings with the DISCO Index in R

cs.LG stat.CO ·2026-11-18 ·Amin Entezari
unusual similarity 0.55
Abstract · 12 pages, 4 figures. R package discoCVI available on CRAN

DISCO is a recent internal cluster validity index for density-based clustering that, unlike earlier indices, also evaluates the quality of noise labels. The discoCVI package makes DISCO available in R. This article describes the design of the package and a typical workflow, in which DISCO is used to compare clusterings and to choose the parameters of HDBSCAN without ground truth, followed by the implementation introduced in version 0.2.0. DISCO is defined through density-connectivity distances between all pairs of points, so direct implementations store several n-by-n matrices. We show that every quantity DISCO needs can be read off the single-linkage merge tree of the mutual-reachability minimum spanning tree, so that the index can be computed exactly with memory that grows linearly with the number of points, while the running time remains quadratic as in the original definition. The implementation is tested against the previous version, agrees with the original Python implementation to within $3 \times 10^{-13}$, and corrects the score of singleton clusters to match the published definition. In benchmarks, discoCVI is 23 to 138 times faster than its previous version for 500 to 4,000 points and 3 to 9 times faster than the Python reference for 500 to 8,000 points, using a fraction of the memory of both, and it scores 100,000 points in about 50 seconds with less than 200 MB of memory.

0.31