Efficient Hypergraph Pattern Matching via Match-and-Filter and Intersection Constraint
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914213508677632 |
|---|---|
| author | Song, Siwoo Shin, Wonseok Park, Kunsoo Italiano, Giuseppe F. Yang, Zhengyi Zhang, Wenjie |
| author_facet | Song, Siwoo Shin, Wonseok Park, Kunsoo Italiano, Giuseppe F. Yang, Zhengyi Zhang, Wenjie |
| contents | A hypergraph is a generalization of a graph, in which a hyperedge can connect multiple vertices, modeling complex relationships involving multiple vertices simultaneously. Hypergraph pattern matching, which is to find all isomorphic embeddings of a query hypergraph in a data hypergraph, is one of the fundamental problems. In this paper, we present a novel algorithm for hypergraph pattern matching by introducing (1) the intersection constraint, a necessary and sufficient condition for valid embeddings, which significantly speeds up the verification process, (2) the candidate hyperedge space, a data structure that stores potential mappings between hyperedges in the query hypergraph and the data hypergraph, and (3) the Match-and-Filter framework, which interleaves matching and filtering operations to maintain only compatible candidates in the candidate hyperedge space during backtracking. Experimental results on real-world datasets demonstrate that our algorithm significantly outperforms the state-of-the-art algorithms, by up to orders of magnitude in terms of query processing time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_10621 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Hypergraph Pattern Matching via Match-and-Filter and Intersection Constraint Song, Siwoo Shin, Wonseok Park, Kunsoo Italiano, Giuseppe F. Yang, Zhengyi Zhang, Wenjie Databases Data Structures and Algorithms A hypergraph is a generalization of a graph, in which a hyperedge can connect multiple vertices, modeling complex relationships involving multiple vertices simultaneously. Hypergraph pattern matching, which is to find all isomorphic embeddings of a query hypergraph in a data hypergraph, is one of the fundamental problems. In this paper, we present a novel algorithm for hypergraph pattern matching by introducing (1) the intersection constraint, a necessary and sufficient condition for valid embeddings, which significantly speeds up the verification process, (2) the candidate hyperedge space, a data structure that stores potential mappings between hyperedges in the query hypergraph and the data hypergraph, and (3) the Match-and-Filter framework, which interleaves matching and filtering operations to maintain only compatible candidates in the candidate hyperedge space during backtracking. Experimental results on real-world datasets demonstrate that our algorithm significantly outperforms the state-of-the-art algorithms, by up to orders of magnitude in terms of query processing time. |
| title | Efficient Hypergraph Pattern Matching via Match-and-Filter and Intersection Constraint |
| topic | Databases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.10621 |