Conference proceeding
Matcha: A Language and Compiler for Backtracking-Based Subgraph Matching
Proceedings - IEEE International Parallel and Distributed Processing Symposium, pp.1154-1165
International Parallel and Distributed Processing Symposium IPDPS
06/03/2025
DOI: 10.1109/IPDPS64566.2025.00105
Abstract
Subgraph matching is one of the most fundamental tasks in graph analytics. Numerous algorithms and systems have been proposed for the task. However, due to the diverse optimizations proposed in previous work and their targeting of different hardware, comparing and integrating existing techniques has become increasingly challenging. In this work, we propose Matcha, a domain-specific language for implementing subgraph matching algorithms. Compared to previous systems, Matcha provides a lower-level programming interface that allows users to express a wider variety of subgraph matching algorithms. This simplifies the comparisons of existing techniques and facilitates the development of new algorithms. We implement a compiler that translates and optimizes Matcha programs into C++/CUDA code for CPU and GPU execution. Our experiments show that Matcha can readily reproduce the performance of state-of-the-art subgraph matching systems. By incorporating additional optimizations, Matcha can achieve speedups up to 60x against the existing systems.
Details
- Title: Subtitle
- Matcha: A Language and Compiler for Backtracking-Based Subgraph Matching
- Creators
- Yihua Wei - University of IowaLihan Hu - University of IowaPeng Jiang - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings - IEEE International Parallel and Distributed Processing Symposium, pp.1154-1165
- Series
- International Parallel and Distributed Processing Symposium IPDPS
- DOI
- 10.1109/IPDPS64566.2025.00105
- ISSN
- 1530-2075
- eISSN
- 1530-2075
- Publisher
- IEEE
- Grant note
- NSF: CNS-2311610, CNS-2310423
This work was supported by NSF award CNS-2311610 and CNS-2310423.
- Language
- English
- Date published
- 06/03/2025
- Academic Unit
- Computer Science
- Record Identifier
- 9984927087102771
Metrics
5 Record Views