by Matthias Barkowsky, Holger Giese
Abstract:
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 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.
Reference:
Hybrid Search Plan Generation for Generalized Graph Pattern Matching (Matthias Barkowsky, Holger Giese), In Graph Transformation - 12th International Conference, ICGT 2019, Held as Part of STAF 2019, Eindhoven, The Netherlands, July 15-16, 2019, Proceedings (Esther Guerra, Fernando Orejas, eds.), 2019.
Bibtex Entry:
@InProceedings{Barkowsky+2019,
AUTHOR = {Barkowsky, Matthias and Giese, Holger},
TITLE = {{Hybrid Search Plan Generation for Generalized Graph Pattern Matching}},
YEAR = {2019},
BOOKTITLE = {Graph Transformation - 12th International Conference, ICGT 2019, Held as Part of STAF 2019, Eindhoven, The Netherlands, July 15-16, 2019, Proceedings},
PAGES = {212-229},
EDITOR = {Guerra, Esther and Orejas, Fernando},
URL = {www.doi.org/10.1007/978-3-030-23611-3_13},
OPTacc_url = {},
PDF = {uploads/pdf/Barkowsky+2019_Barkowsky-Giese2019_Chapter_HybridSearchPlanGenerationForG.pdf},
SLIDES = {uploads/slides/Barkowsky+2019_presentation.pdf},
ABSTRACT = {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 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.}
}