加速
计算机科学
算法
SIMD公司
矩阵表示法
理论计算机科学
并行计算
有机化学
化学
群(周期表)
作者
Kaushik Ravichandran,Akshara Subramaniasivam,P Aishwarya,Nikesh Kumar
出处
期刊:Advances in Computers
日期:2023-01-01
卷期号:: 233-250
标识
DOI:10.1016/bs.adcom.2021.10.003
摘要
Triangle counting is a cornerstone operation used in large graph analytics. Hash-based algorithms for triangle counting fail to take advantage of available vectorization in modern processors. Linear algebraic-based methods often involve sparse matrix multiplication which is inherently expensive. Nonlinear algebraic methods have a slow implementation and count each triangle multiple times which is then rescaled to obtain the exact triangle count. We propose a fast vector instruction implementation of a set operation-based triangle counting algorithm, which avoids matrix multiplication and finds the exact triangle count directly. Our implementation outperforms reference implementations proposed by the MIT graph challenge and miniTri when tried on about 40 graphs from the SNAP large network dataset, giving a speedup ranging from 41× to more than 1500×. A comparison against existing state-of-the-art techniques gave a speedup of 3× on average. We additionally show that this algorithm can easily be plugged into graph frameworks that either use or can be modified to use compressed sparse row like representation, to give faster compute times. We also propose an optimization to the k truss decomposition algorithm that can be used with the optimized triangle counting algorithm to give better performance.
科研通智能强力驱动
Strongly Powered by AbleSci AI