TY  - JOUR
A1  - Barkowsky, Matthias
A1  - Giese, Holger
T1  - Hybrid search plan generation for generalized graph pattern matching
JF  - Journal of logical and algebraic methods in programming
N2  - In recent years, the increased interest in application areas such as social networks has resulted in a rising popularity of graph-based approaches for storing and processing large amounts of interconnected data. To extract useful information from the growing network structures, efficient querying techniques are required.
In this paper, we propose an approach for graph pattern matching that allows a uniform handling of arbitrary constraints over the query vertices. Our technique builds on a previously introduced matching algorithm, which takes concrete host graph information into account to dynamically adapt the employed search plan during query execution. The dynamic algorithm is combined with an existing static approach for search plan generation, resulting in a hybrid technique which we further extend by a more sophisticated handling of filtering effects caused by constraint checks. We evaluate the presented concepts empirically based on an implementation for our graph pattern matching tool, the Story Diagram Interpreter, with queries and data provided by the LDBC Social Network Benchmark. Our results suggest that the hybrid technique may improve search efficiency in several cases, and rarely reduces efficiency.
KW  - graph pattern matching
KW  - search plan generation
Y1  - 2020
U6  - https://doi.org/10.1016/j.jlamp.2020.100563
SN  - 2352-2208
VL  - 114
PB  - Elsevier
CY  - New York
ER  -