GLUMIN: Fast Connectivity Check Based on LUTs For Efficient Graph Pattern Mining
Graph Pattern Mining (GPM) has made significant progress in recent years, opening up a range of big data applications. However, GPM applications are memory-intensive as they require a tremendous amount of pair checking, which involves enumerating all possible vertex pairs and checking their connectivity or counting the common neighbors of each pair. Adjacent list or CSR format is widely used in recent GPM systems to overcome the sparsity of real-world graph, at the cost of sacrificing the ability to query the connectivity of two vertices in 𝑂 (1) compared with raw adjacent matrix. In this paper, we rethink the format to store graph in GPM systems, by partial ‘restoring’ graph from CSR to adjacent matrix, we can significantly accelerate checking connectivity or counting common neighbors during searching process. However, directly storing graph in adjacent matrix is cost-prohibitive, thus we propose GLUMIN, by selectively constructing lookup table (LUT) at the runtime, which holds the connectivity that can be repeatedly retrieved at low-cost. The LUTs are compressed and tailored to fit the hierarchical memory architecture like GPU shared memory or CPU cache. We adapt GLUMIN technique to several SOTA GPM systems like AutoMine, G2Miner and GraphFold, bring two order of magnitude speedup to them on 135 different types graphs and 24 patterns, demonstrating the general applicability and significance of our methods.
Wed 5 MarDisplayed time zone: Pacific Time (US & Canada) change
10:00 - 11:20 | |||
10:00 20mTalk | Popcorn: Accelerating Kernel K-means on GPUs through Sparse Linear Algebra Main Conference Julian Bellavita Cornell University, Thomas Pasquali University of Trento, Laura Del Rio University of Trento, Flavio Vella Free University of Bozen, Giulia Guidi Cornell University | ||
10:20 20mTalk | Swift Unfolding of Communities: GPU-Accelerated Louvain Algorithm Main Conference Zhibin Wang Nanjing University, Xi Lin Nanjing University, Xue Li Alibaba Group, Pinhuan Wang Rutgers, The State University of New Jersey, Ziheng Meng Nanjing University, Hang Liu Rutgers, The State University of New Jersey, Chen Tian Nanjing University, Sheng Zhong Nanjing University | ||
10:40 20mTalk | GLUMIN: Fast Connectivity Check Based on LUTs For Efficient Graph Pattern Mining Main Conference Weichen Cao Institute of Computing Technology, Chinese Academy of Sciences, Ke Meng Chinese Academy of Sciences, linzhiheng Institute of Computing Technology, Chinese Academy of Sciences, Guangming Tan Chinese Academy of Sciences(CAS) | ||
11:00 20mTalk | Improving Tridiagonalization Performance on GPU Architectures Main Conference WangHansheng University of Electronic Science and Technology of China, Zhekai Duan University of Edinburgh, Zitian Zhao University of Electronic Science and Technology of China, Siqi Wu University of Electronic Science and Technology of China, Saiqi Zheng Xi'an Jiaotong-Liverpool University, Qiao Li University of Electronic Science and Technology of China, Xu Jiang University of Electronic Science and Technology of China, Shaoshuai Zhang | ||