Efficiently Computing Homomorphic Matches of Hybrid Pattern Queries on Large Graphs

Xiaoying Wu, Dimitri Theodoratos, Dimitrios Skoutas, Michael Lan

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

2 Scopus citations

Abstract

In this paper, we address the problem of efficiently finding homomorphic matches for hybrid patterns over large data graphs. Finding matches for patterns in data graphs is of fundamental importance for graph analytics. In hybrid patterns, each edge may correspond either to an edge or a path in the data graph, thus allowing for higher expressiveness and flexibility in query formulation. We introduce the concept of answer graph to compactly represent the query results and exploit computation sharing. We design a holistic bottom-up algorithm called GPM, which greatly reduces the number of intermediate results, leading to significant performance gains. GPM directly processes child constraints in the given query instead of resorting to a post-processing procedure. An extensive experimental evaluation using both real and synthetic datasets shows that our methods evaluate hybrid patterns up to several orders of magnitude faster than existing algorithms and exhibit much better scalability.

Original languageEnglish (US)
Title of host publicationBig Data Analytics and Knowledge Discovery - 21st International Conference, DaWaK 2019, Proceedings
EditorsCarlos Ordonez, Il-Yeol Song, Gabriele Anderst-Kotsis, Ismail Khalil, A Min Tjoa
PublisherSpringer
Pages279-295
Number of pages17
ISBN (Print)9783030275198
DOIs
StatePublished - 2019
Event21st International Conference on Big Data Analytics and Knowledge Discovery, DaWaK 2019 - Linz, Austria
Duration: Aug 26 2019Aug 29 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11708 LNCS

Conference

Conference21st International Conference on Big Data Analytics and Knowledge Discovery, DaWaK 2019
Country/TerritoryAustria
CityLinz
Period8/26/198/29/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Efficiently Computing Homomorphic Matches of Hybrid Pattern Queries on Large Graphs'. Together they form a unique fingerprint.

Cite this