Inverted-File k-Means Clustering: Performance Analysis
Inverted-File k-Means Clustering: Performance Analysis
复制标题
DOI：
--
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
K. Aoyama;Kazumi Saito;Tetsuo Ikeda
中科院分区：
文献类型：
--
作者：
K. Aoyama;Kazumi Saito;Tetsuo Ikeda
提出了一种倒排文件k-均值聚类算法(IVF)，该算法适用于具有潜在多个类的大规模稀疏数据集。在给定这样的数据集的情况下，试管受精高效地以高速和低内存消耗工作，这保持了与标准劳埃德算法相同的解决方案。高性能源于两种截然不同的数据表示。一种是对象和平均特征向量的稀疏表达式。另一种是一组平均特征向量的倒排文件数据结构。为了确认这些表示的效果，我们设计了三种算法，使用不同的数据结构和表达式进行比较。实验证明，在现代计算机系统中，当IVF算法应用于大规模真实文档数据集时，其性能优于所设计的算法。现代计算机系统配备了超标量无序处理器和深层次存储系统。我们还介绍了一个简单而实用的每指令时钟周期(CPI)模型，用于速度-性能分析。分析结果表明，IVF抑制了三个性能降级因素：高速缓存未命中、分支错误预测和已完成指令的数量。
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.