EUVIMEDEUVIMED entdecken
Crossref

CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination

Linglin Yang, Xunbin Su, Lei Zou, Xiangyang Gou, Yinnian Lin

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →