This paper presents an architecture-friendly k-means clustering algorithm called SIVF for a large-scale and high-dimensional sparse data set. Algorithm efficiency on time is often measured by the number of costly operations such as similarity calculations. In practice, however, it depends greatly on how the algorithm adapts to an architecture of the computer system which it is executed on. Our proposed SIVF employs invariant centroid-pair based filter (ICP) to decrease the number of similarity calculations between a data object and centroids of all the clusters. To maximize the ICP performance, SIVF exploits for a centroid set an inverted-file that is structured so as to reduce pipeline hazards. We demonstrate in our experiments on real large-scale document data sets that SIVF operates at higher speed and with lower memory consumption than existing algorithms. Our performance analysis reveals that SIVF achieves the higher speed by suppressing performance degradation factors of the number of cache misses and branch mispredictions rather than less similarity calculations.


翻译:本文展示了一种结构友好的K- means群集算法,称为SIVF,用于大规模和高维分散数据集。对数值的及时效率通常以类似计算等费用高昂的操作数量来衡量。然而,在实践中,它在很大程度上取决于算法如何适应计算机系统的结构。我们提议的SIVF使用基于无变量的中子机器人过滤器(ICP)来减少数据对象与所有分类组的类固醇之间的相似性计算数量。为了最大限度地提高比较方案性能,SIVF利用一个为减少管道危险而设置的反向文件。我们在实际大规模文件数据集的实验中表明,SIVF的运行速度高于现有算法,记忆消耗也低于现有的算法。我们的业绩分析表明,SIVF通过抑制缓存误差和分支误差数量的性能降解因素,而不是较少相似性计算,从而达到更高的速度。

0
下载
关闭预览

相关内容

【ACML2020】张量网络机器学习:最近的进展和前沿,109页ppt
专知会员服务
54+阅读 · 2020年12月15日
【干货书】机器学习速查手册,135页pdf
专知会员服务
120+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
105+阅读 · 2020年5月3日
【Strata Data Conference】用于自然语言处理的深度学习方法
专知会员服务
48+阅读 · 2019年9月23日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
14+阅读 · 2019年4月13日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
干货 | 自然语言处理(2)之浅谈向量化与Hash-Trick
机器学习算法与Python学习
3+阅读 · 2017年12月13日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年5月25日
Arxiv
0+阅读 · 2021年5月19日
Meta-Learning to Cluster
Arxiv
17+阅读 · 2019年10月30日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
14+阅读 · 2019年4月13日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
干货 | 自然语言处理(2)之浅谈向量化与Hash-Trick
机器学习算法与Python学习
3+阅读 · 2017年12月13日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员