Leveraging Double Simulation to Efficiently Evaluate Hybrid Patterns on Data Graphs

Xiaoying Wu, Dimitri Theodoratos, Dimitrios Skoutas, Michael Lan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Labeled graphs are used to represent entities and their relationships in a plethora of Web applications. Graph pattern matching is a fundamental operation for the analysis and exploration of data graphs. In this paper, we address the problem of efficiently finding homomorphic matches for hybrid patterns, where each edge may be mapped either to an edge or to a path, thus allowing for higher expressiveness and flexibility in query formulation. We design a novel holistic graph simulation-based algorithm, called GraphMatch-Sim, which leverages simulation to precisely identify, in advance, all the graph nodes that participate in the pattern matches returned. GraphMatch-Sim can flexibly employ any reachability index as a plug-in component. Unlike existing methods, it produces no redundant intermediate results, thus achieving worst-case optimality. An extensive experimental evaluation on both real and synthetic datasets shows that our method evaluates hybrid patterns orders of magnitude faster than existing algorithms and has much better scalability.

Original languageEnglish (US)
Title of host publicationWeb Information Systems Engineering – WISE 2020 - 21st International Conference, Proceedings
EditorsZhisheng Huang, Wouter Beek, Hua Wang, Yanchun Zhang, Rui Zhou
PublisherSpringer Science and Business Media Deutschland GmbH
Pages255-269
Number of pages15
ISBN (Print)9783030620042
DOIs
StatePublished - 2020
Event21st International Conference on Web Information Systems Engineering, WISE 2020 - Amsterdam, Netherlands
Duration: Oct 20 2020Oct 24 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12342 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Web Information Systems Engineering, WISE 2020
CountryNetherlands
CityAmsterdam
Period10/20/2010/24/20

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Leveraging Double Simulation to Efficiently Evaluate Hybrid Patterns on Data Graphs'. Together they form a unique fingerprint.

Cite this