BEEP: Balanced Efficient subgraph Enumeration in Parallel
Published in 52nd International Conference on Parallel Processing (ICPP), 2023
BEEP is a state-of-the-art subgraph enumerator that combines parallel GPU processing and algorithmic improvements for high performance. It surpasses existing GPU enumerators based on Breadth First Search (BFS) by adopting Depth First Search (DFS) and addressing computational inefficiencies and load imbalances. With geometric mean speedups of up to 10.52× across data graphs and 6.81× across queries, and maximum speedups of 33.46×, BEEP is currently the fastest subgraph enumerator available. Additionally, a multi-GPU implementation demonstrates nearly linear scalability with the number of devices.
ACM Reference Format:
Samiran Kawtikwar, Mohammad Almasri, Wen-Mei Hwu, Rakesh Nagi, and Jinjun Xiong. 2023. BEEP: Balanced Efficient subgraph Enumeration in Parallel. In Proceedings of the 52nd International Conference on Parallel Processing (ICPP ‘23). Association for Computing Machinery, New York, NY, USA, 142–152. https://doi.org/10.1145/3605573.3605653.
Source code: [GitHub] <a href=https://github.com/researchgroup-zx93920/BEEP>(https://github.com/researchgroup-zx93920/BEEP)</a>