CS Paper Radar

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

Amin Entezari

cs.LG stat.CO ·submitted 2026-11-18 19:52 UTC · v1
unusual

Abstract

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.

Comment
12 pages, 4 figures. R package discoCVI available on CRAN

Closest papers

Nearest neighbours by meaning across the whole index.

Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems

cs.DS ·2026-09-28 ·David García-Soriano, Atsushi Miyauchi
similarity 0.55
Abstract

The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most $k$ clusters using $k$ independent Gaussian vectors. Its analysis hinges on the collision probability $P_k(ρ)$ that two nodes whose SDP vectors have inner product $ρ$ are assigned to the same cluster. No tractable closed form for $P_k$ is known for $k\geq 4$, making it difficult to certify approximation guarantees and hindering the systematic search for better algorithms. We develop a Hermite-coefficient certification framework to derive accurate and tractable bounds on $P_k$. Using the Hermite expansion of Gaussian noise stability, we express $P_k$ as a power series with nonnegative coefficients, reduce these coefficients to one-dimensional Gaussian integrals, and certify finitely many of them, yielding rigorous bounds on $P_k$ over the entire correlation range. Our framework yields strengthened polynomial-time approximations for several clustering problems. For MaxAgree Correlation Clustering, we derive a $0.7818$-approximation, the first improvement in two decades over the $0.7666$ ratio of Swamy (2004). We also improve the best known ratios for the variant with at most $K$ clusters, MaxAgree$[K]$ (e.g., from $0.77$ to $0.8151$ for $K=3$). For Max $K$-Cut we resolve, via a structural property of the Hermite expansion, a conjecture of de Klerk et al. (2004) characterizing the Frieze--Jerrum approximation ratio for every $K\ge3$; we show that this ratio is tight, and determine it to within $10^{-6}$ accuracy for $K\le16$. Finally, we reduce the additive approximation error for modularity maximization from $0.42084$ (Kawase et al., 2021) to $0.3790$. On the hardness side, we show that approximating Maxagree within $0.802+ε$ is Unique Games-hard via a construction in Gaussian space analyzed by Borell's inequality.

0.39

HDLouvain: High-Throughput Incremental Clustering for Hyperdimensional Data

cs.AR ·2026-10-22 ·Beenish Gul, Mahbod Afarin, Farhat Ahmed, Sumukh Pinge, Tsung-Han Lu +2 more
benchmark similarity 0.55
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.

0.26

A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum Clustering

cs.DS cs.CC ·2026-10-10 ·Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, Samson Zhou
similarity 0.54
Abstract

Metric $k$-minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achieved fornother clustering criteria in the past three decades. In this paper we give an efficient approximation scheme for this problem that runs in sublinear time for mildly increasing $k$, and thus is fixed parameter tractable with respect to the parameter $k$. We complement this result by showing that similar algorithms are unlikely to exist for the closely related problems $k$-median and balanced $k$-median, assuming popular fine-grained complexity conjectures. Specifically, we show that no sublinear time algorithm with small approximation factors can exist even for $2$-median and balanced $2$-median. It was previously known that no efficient PTAS can exist for $k$-median and our results show a strong and perhaps surprising separation between the $k$-minsum clustering problem and $k$-median even in the sublinear regime. Our upper bounds improve qualitatively upon decades old results. Our lower bounds establish the first use of the Distributed PCP framework to clustering problems.

0.14

GPU-Accelerated Construction of the Gabriel Graph: Parallelization Strategies and Applications to Large-Margin Classification and Graph-Based Clustering

cs.DC cs.AIcs.LG ·2026-10-20 ·Diego Sanches Nere dos Santos, Luiz Carlos Bambirra Torres
benchmark similarity 0.54
Abstract · 12 pages, 3 figures, 1 table

The Gabriel graph is a proximity graph widely used in computational geometry and geometric machine learning, underlying large-margin classifiers and, as we show in this work, density-aware clustering methods. Its construction, however, has cubic time complexity $O(N^3)$ in the naive formulation, which severely limits its use on datasets beyond a few thousand samples. This paper presents a set of GPU parallelization strategies, implemented in CUDA, that make Gabriel graph construction practical at scale. We introduce (i) an implicit closed-form mapping from a linear thread index to the corresponding vertex pair $(i,j)$, which removes the need for an explicit $O(N^2)$ adjacency structure and lets every thread locate its pair in constant time and constant memory; (ii) a two-pass, bitmask-based, atomically-compacted edge-list construction that produces a dense edge array proportional only to the number of edges actually found; and (iii) a thread-coarsening strategy in which each thread evaluates several candidate pairs, trading launch and scheduling overhead against load balance. We evaluate these strategies on the acceleration of a Gabriel-graph-based large-margin classifier (NN-clas) and on a novel Gabriel-graph clustering algorithm that identifies connected components on a residual graph and performs GPU-parallel Union-Find with hierarchical edge-based merging. On 14 public benchmark datasets, the GPU implementation reduces Gabriel graph construction time by two to nearly four orders of magnitude relative to a sequential CPU baseline (up to 8484x), without loss of classification accuracy, and the proposed clustering method is statistically competitive with DBSCAN on the topological validity index Dunn while eliminating the need for an explicit density radius parameter.

0.33

Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy

cs.LG ·2026-08-14 ·Johanna Hillebrand, Jan Höckendorff, Jürgen Kusche, Kelin Luo, Heiko Röglin +3 more
theory similarity 0.54
Abstract

Constrained optimization extends classical optimization by integrating side information, making it widely applicable across scientific and engineering domains. Consider a setting where we measure variables at different physical locations. When grouping these measurements, we often want clusters that are both internally similar and physically coherent. Thus, we have a constrained clustering problem where the constraint models coherence. Motivated by an application in geodesy, where contiguous regions of the sea surface must be identified for principal component analysis, we introduce the Connected Subspace Clustering problem: given high-dimensional points and a connectivity graph, partition them into $k$ connected clusters, minimizing their total squared distance to the clusters' best-fit $m'$-dimensional affine subspaces. We prove that, even for $m' = 0$ and a grid graph with holes, the problem is NP-hard to approximate within $Ω(n^{1/2-\varepsilon})$ for every $\varepsilon>0$, where $n$ is the number of measurements. We then introduce an efficient Lloyd-style heuristic that alternates subspace fitting with an iterative merging procedure to enforce connectivity. Our method returns exactly $k$ connected regions by construction, whereas unconstrained methods leave up to $1{,}966$ disconnected fragments at higher cost. In a study of 160 configurations on global sea level time series, our merging-based repair is the strongest of four strategies in $73.75\%$ of cases, and consistently outperforms competitors such as (connected) Ward's method across all tested cluster counts. The resulting regions isolate signals aligning with climate indices such as the El Nino-Southern Oscillation and Indian Ocean Dipole. Although developed for geodesy, the approach applies to other spatially embedded multivariate time series, such as climate fields, remote sensing, neuroimaging, and sensor networks.

0.04

Topological Equivalence of Spectral and Density Cluster Hierarchies

cs.LG ·2026-10-22 ·Sajjad Hashemian
similarity 0.53
Abstract

We compare two canonical ways to recover hierarchical clustering from an underlying density $f$: the \emph{density cluster tree} given by connected components of superlevel sets $\{f\geλ\}$, and a \emph{spectral hierarchy} obtained by applying single linkage to diffusion distances induced by a Laplacian operator. We give conditions under which, at an appropriate diffusion time, the diffusion hierarchy is \emph{topologically equivalent} to the density cluster tree up to a monotone rescaling of heights. It further shows that a $k$-NN graph implementation inherits this equivalence from uniform approximation of diffusion distances, yielding a finite-sample reduction from spectral graph constructions to density-level-set topology.

0.25

Streaming algorithms for computing coresets and $k$-median clustering in the Hamming space

cs.DS ·2026-08-25 ·Taha El Ghazi, Jonas Ellert, Chien-Chung Huang, Tatiana Starikovskaya
published similarity 0.53
Abstract · Accepted to WAOA 2026

Clustering is one of the most fundamental tools in data analysis, allowing large datasets to be summarized by a small number of representative points. Given a metric space $(\mathcal{X}, \mathbb{d})$ and a set $S$ of $n$ points in this space, the continuous $k$-median clustering problem asks to find a set $C$ of $k$ points that minimizes the objective function $\sum_{s\in S} \mathbb{d}(s,C)$. When $\mathcal{X} = Σ^\ell$ is the set of strings of length $\ell$ and $\mathbb{d}$ is the Hamming distance, the continuous $k$-median clustering problem is known to be W[1]-hard when parameterized by $k$. In this work, we present the first $(1+\varepsilon)$-approximation algorithm for this problem with FPT runtime $2^{\mathrm{poly}(\varepsilon^{-1},k)} \cdot n\ell \mathrm{polylog} \; n$. An additional feature of the algorithm is that it can be implemented in streaming, requiring only $\tilde{O}_\varepsilon(\ell k + k^2)$ space. As an auxiliary tool of independent interest, we show the first streaming algorithm for computing an $\varepsilon$-coreset for continuous $k$-median clustering under the Hamming

0.42

Accelerating FastDEC Clustering Algorithm with GPUs

cs.LG ·2026-11-02 ·Mi Li, Eibe Frank, Bernhard Pfahringer
hot direction similarity 0.53
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