×

Hybrid search plan generation for generalized graph pattern matching. (English) Zbl 1451.68198

Summary: 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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68P10 Searching and sorting

Software:

GrGen; Henshin
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Angles, R., A comparison of current graph database models, (2012 IEEE 28th International Conference on Data Engineering Workshops (2012), IEEE), 171-177
[2] Barkowsky, M.; Giese, H., Hybrid search plan generation for generalized graph pattern matching, (International Conference on Graph Transformation (2019), Springer), 212-229
[3] Beyhl, T.; Blouin, D.; Giese, H.; Lambers, L., On the operationalization of graph queries with generalized discrimination networks, (Echahed, R.; Minas, M., Proceedings of the 9th International Conference on Graph Transformations (2016), Springer), 170-186 · Zbl 1344.68063
[4] Giese, H.; Hildebrandt, S.; Seibel, A., Improved flexibility and scalability by interpreting story diagrams, Electron. Commun. EASST, 18 (2009)
[5] Varró, G.; Deckwerth, F.; Wieber, M.; Schürr, A., An algorithm for generating model-sensitive search plans for EMF models, (International Conference on Theory and Practice of Model Transformations (2012), Springer), 224-239
[6] Erling, O.; Averbuch, A.; Larriba-Pey, J.; Chafi, H.; Gubichev, A.; Prat, A.; Pham, M.-D.; Boncz, P., The LDBC social network benchmark: interactive workload, (Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (2015), ACM), 619-630
[7] Geiß, R.; Batz, G. V.; Grund, D.; Hack, S.; Szalkowski, A., GrGen: a fast SPO-based graph rewriting tool, (International Conference on Graph Transformation (2006), Springer), 383-397 · Zbl 1156.68427
[8] Ehrig, H.; Ehrig, K.; Prange, U.; Taentzer, G., Fundamentals of Algebraic Graph Transformation (2006), Springer · Zbl 1095.68047
[9] Bi, F.; Chang, L.; Lin, X.; Qin, L.; Zhang, W., Efficient subgraph matching by postponing Cartesian products, (Proceedings of the 2016 International Conference on Management of Data (2016), ACM), 1199-1214
[10] Arendt, T.; Biermann, E.; Jurack, S.; Krause, C.; Taentzer, G., Henshin: advanced concepts and tools for in-place EMF model transformations, (International Conference on Model Driven Engineering Languages and Systems (2010), Springer), 121-135
[11] Foggia, P.; Sansone, C.; Vento, M., A performance comparison of five algorithms for graph isomorphism, (Proceedings of the 3rd IAPR TC-15 Workshop on Graph-Based Representations in Pattern Recognition (2001)), 188-199
[12] Shang, H.; Zhang, Y.; Lin, X.; Yu, J. X., Taming verification hardness: an efficient algorithm for testing subgraph isomorphism, Proc. VLDB Endow., 1, 1, 364-375 (2008)
[13] Hildebrandt, S., On the Performance and Conformance of Triple Graph Grammar Implementations (June 2014), Hasso Plattner Institute at the University of Potsdam, Ph.D. thesis
[14] Haralick, R. M.; Elliott, G. L., Increasing tree search efficiency for constraint satisfaction problems, Artif. Intell., 14, 3, 263-313 (1980)
[15] EMF, Eclipse modeling framework (2019)
[16] Gamma, E., Design Patterns: Elements of Reusable Object-Oriented Software (1995), Pearson Education India
[17] Ullmann, J. R., An algorithm for subgraph isomorphism, J. ACM, 23, 1, 31-42 (1976) · Zbl 0323.05138
[18] Cordella, L. P.; Foggia, P.; Sansone, C.; Vento, M., An improved algorithm for matching large graphs, (3rd IAPR-TC15 Workshop on Graph-Based Representations in Pattern Recognition (2001)), 149-159
[19] Zündorf, A., Graph pattern matching in PROGRES, (International Workshop on Graph Grammars and Their Application to Computer Science (1994), Springer), 454-468
[20] Búr, M.; Ujhelyi, Z.; Horváth, Á.; Varró, D., Local search-based pattern matching features in EMF-IncQuery, (International Conference on Graph Transformation (2015), Springer), 275-282
[21] Varró, D.; Bergmann, G.; Hegedüs, Á.; Horváth, Á.; Ráth, I.; Ujhelyi, Z., Road to a reactive and incremental model transformation platform: three generations of the viatra framework, Softw. Syst. Model., 15, 3, 609-629 (2016)
[22] Horváth, Á.; Varró, G.; Varró, D., Generic search plans for matching advanced graph patterns, Electron. Commun. EASST, 6 (2007)
[23] Bak, C.; Plump, D., Rooted graph programs, (Proceedings of International Workshop on Graph-Based Tools. Proceedings of International Workshop on Graph-Based Tools, GraBaTs 2012, vol. 54 (2012))
[24] Beyhl, T., A framework for incremental view graph maintenance (2018), Hasso Plattner Institute at the University of Potsdam, Ph.D. thesis
[25] Fan, W.; Wang, X.; Wu, Y., Incremental graph pattern matching, ACM Trans. Database Syst., 38, 3, 18 (2013) · Zbl 1321.68243
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.