CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination
Proceedings of the VLDB Endowment · 01.03.2026 · 19 (7) · 1572-1585
DOI: 10.14778/3801059.3801070 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 14.07.2026. Verfasst von Linglin Yang und 4 weiteren Autor:innen. Die Arbeit nennt 50 Literaturangaben.
Abstract (Originalsprache)
Subgraph matching is a fundamental problem in graph analysis with a wide range of applications. However, due to its inherent NP-hardness, enumerating subgraph matches efficiently on large real-world graphs remains highly challenging. Most existing works adopt a depth-first search (DFS) backtracking strategy, where a partial embedding is gradually extended in a DFS manner along a branch of the search trees until either a full embedding is found or no further extension is possible. A major limitation of this paradigm is the significant amount of duplicate computation that occurs during enumeration, which increases the overall runtime. To overcome this limitation, we propose a novel subgraph matching algorithm, CEMR. It incorporates two techniques to reduce duplicate extensions: common extension merging , which leverages a black-white vertex encoding, and common extension reusing , which employs common extension buffers. In addition, we design two pruning techniques to discard unpromising search branches. Extensive experiments on real-world datasets and diverse query workloads demonstrate that CEMR outperforms state-of-the-art subgraph matching methods.
Zitieren
APA
Yang, L., Su, X., Zou, L., Gou, X., & Lin, Y. (2026). CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination. Proceedings of the VLDB Endowment, 19(7), 1572-1585. https://doi.org/10.14778/3801059.3801070
Vancouver
Yang L, Su X, Zou L, Gou X, Lin Y. CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination. Proceedings of the VLDB Endowment. 2026;19(7):1572-1585. doi:10.14778/3801059.3801070
BibTeX
@article{Yang2026,
author = {Yang, Linglin and Su, Xunbin and Zou, Lei and Gou, Xiangyang and Lin, Yinnian},
title = {CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {7},
pages = {1572--1585},
doi = {10.14778/3801059.3801070}
}
EUVIMED