2020/02/21 by Kazuo Aoyama, Aoyama, Kazuo, Kazumi Saito +3 · 3 citations
Computer Science · Mathematics · #Advanced Clustering Algorithms Research #Advanced Image and Video Retrieval Techniques #Algorithm #Artificial intelligence #Cache #Caching and Content Delivery #Cluster analysis #Computer science #Data structure #FOS: Computer and information sciences #Inverted index #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Operating system #Parallel computing #Search engine indexing #Set (abstract data type) #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2002.09094
published in arXiv (Cornell University) (Cornell University) · 15 pages, 20 figures
arxiv created 2020/02/21 · openalex publication_date 2020/02/21 · arxiv updated 2020/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
This paper presents an inverted-file k-means clustering algorithm (IVF) suitable for a large-scale sparse data set with potentially numerous classes. Given such a data set, IVF efficiently works at high-speed and with low memory consumption, which keeps the same solution as a standard Lloyd's algorithm. The high performance arises from two distinct data representations. One is a sparse expression for both the object and mean feature vectors. The other is an inverted-file data structure for a set of the mean feature vectors. To confirm the effect of these representations, we design three algorithms using distinct data structures and expressions for comparison. We experimentally demonstrate that IVF achieves better performance than the designed algorithms when they are applied to large-scale real document data sets in a modern computer system equipped with superscalar out-of-order processors and a deep hierarchical memory system. We also introduce a simple yet practical clock-cycle per instruction (CPI) model for speed-performance analysis. Analytical results reveal that IVF suppresses three performance degradation factors: the numbers of cache misses, branch mispredictions, and the completed instructions.