Proceedings of the ACM on Management of Data · 2023 · 25 citations · 38 references
ComputingComputer EngineeringComputer ScienceAlgorithmsData StructuresParallel ComputingData ParallelismGraph AlgorithmsGraphics Processing Unit ArchitectureGraphics Processing Unit ComputingGraphics Processing UnitsMemory Hierarchy OptimizationBreadth-first SearchCuckoo SearchDepth-first SearchGpu Parallel AlgorithmsGraph MatchingGraph ProcessingMatching AlgorithmsTrie Data Structures
Subgraph matching is a basic operation in graph analytics, finding all occurrences of a query graph Q in a data graph G. A common approach is to first filter out non-candidate vertices in G, and then order the vertices in Q to enumerate results. Recent work has started to utilize the GPU to accelerate subgraph matching. However, the effectiveness of current GPU-based filtering and ordering methods is limited, and the result enumeration often runs out of memory quickly. To address these problems, we propose EGSM, an efficient approach to GPU-based subgraph matching. Specifically, we design a data structure Cuckoo trie to support dynamic maintenance of candidates for filtering, and order query vertices based on estimated numbers of candidate vertices on the fly. Furthermore, we perform a hybrid breadth-first and depth-first search with memory management for result enumeration. Consequently, EGSM significantly outperforms the state-of-the-art GPU-accelerated algorithms, including GSI and CuTS.
38
An Algorithm for Subgraph Isomorphism
J. R. Ullmann · Journal of the ACM · 1976 · 2.3K citations · Full text
Rasmus Pagh, Flemming Friche Rodler · Journal of Algorithms · 2004 · 1.1K citations
Haichuan Shang, Ying Zhang, Xuemin Lin et al. · Proceedings of the VLDB Endowment · 2008 · 392 citations