Hybrid search plan generation for generalized graph pattern matching
- 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, withIn 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.…
Author details: | Matthias BarkowskyORCiD, Holger GieseORCiDGND |
---|---|
DOI: | https://doi.org/10.1016/j.jlamp.2020.100563 |
ISSN: | 2352-2208 |
Title of parent work (English): | Journal of logical and algebraic methods in programming |
Publisher: | Elsevier |
Place of publishing: | New York |
Publication type: | Article |
Language: | English |
Date of first publication: | 2020/05/27 |
Publication year: | 2020 |
Release date: | 2023/01/05 |
Tag: | graph pattern matching; search plan generation |
Volume: | 114 |
Article number: | 100563 |
Number of pages: | 29 |
Funding institution: | Deutsche ForschungsgemeinschaftGerman Research Foundation (DFG) [GI; 765/8-1] |
Organizational units: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Peer review: | Referiert |