cs.LGNov 2, 2026

Accelerating FastDEC Clustering Algorithm with GPUs

Authors: Mi Li, Eibe Frank, Bernhard Pfahringer

Organizations: Department of Computer Science, University of Waikato, Hamilton, New Zealand.

Abstract

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.

Figures & tables

Explore similar work

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

    Sep 28, 2026Peng Xu, Nihar Koganti, Volodymyr Kindratenko +1ClusteringNon-Negative Matrix Factorization

  2. Accelerating Dynamic Graph Clustering on GPU Architectures with cuGraph

    Aug 4, 2026Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore TraniGPU AccelerationClustering