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

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.