{"ID":2830261,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.10621","arxiv_id":"2512.10621","title":"Efficient Hypergraph Pattern Matching via Match-and-Filter and Intersection Constraint","abstract":"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.","short_abstract":"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 proble...","url_abs":"https://arxiv.org/abs/2512.10621","url_pdf":"https://arxiv.org/pdf/2512.10621v2","authors":"[\"Siwoo Song\",\"Wonseok Shin\",\"Kunsoo Park\",\"Giuseppe F. Italiano\",\"Zhengyi Yang\",\"Wenjie Zhang\"]","published":"2025-12-11T13:19:06Z","proceeding":"cs.DB","tasks":"[\"cs.DB\",\"cs.DS\"]","methods":"[]","has_code":false}