Advertisement
Published in:
2019 | OriginalPaper | Chapter
Efficiently Computing Homomorphic Matches of Hybrid Pattern Queries on Large Graphs
Authors : Xiaoying Wu, Dimitri Theodoratos, Dimitrios Skoutas, Michael Lan
Published in: Big Data Analytics and Knowledge Discovery
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.