Accelerating Spherical K-Means Clustering for Large-Scale Sparse Document Data

doi:10.1109/TKDE.2025.3608264

Accelerating Spherical K-Means Clustering for Large-Scale Sparse Document Data

2025-09-09

0

PRE

AI

DOI：10.1109/TKDE.2025.3608264

Original

Original request for help

Save

Abstract

En 中文

This paper presents an accelerated spherical K-means clustering algorithm for large-scale and high-dimensional sparse document data sets. We design an algorithm working in an architecture-friendly manner (AFM), which is a way of suppressing performance-degradation factors such as the numbers of instructions, branch mispredictions, and cache misses in CPUs of a computer system. For the AFM operation, we leverage universal characteristics (UCs) of the data, which are skewed distributions on data relationships. The UCs indicate that the most part of multiplications for similarity calculations is executed on high-document-frequency terms and the most part of a similarity is obtained by the multiplications regarding a few high mean-feature values. To extract the foregoing specific region on terms and mean-feature values, we construct a mean-inverted index partitioned into three regions by two structural parameters. Our algorithm optimizes the parameters by minimizing the approximate number of the multiplications corresponding to the instructions based on our efficient pruning method, reduces conditional branches by sharing the index structure with all the objects, and keeps in the caches the frequently used data in the foregoing specific region. We experimentally demonstrate that our algorithm efficiently achieves superior speed performance in large-scale documents compared with algorithms using the state-of-the-art techniques.

Keywords:

Algorithm

spherical k-means clustering

large-scale high-dimensional sparse data

data characteristics

data structure

inverted index

computer architecture

Accelerating Spherical K-Means Clustering for Large-Scale Sparse Document Data

Abstract

Journal

Organization

Cited Papers