More Web Proxy on the site http://driver.im/

article

An algorithm for generating model-sensitive search plans for pattern matching on EMF models

Authors:

Gergely Varró,

Frederik Deckwerth,

Andy SchürrAuthors Info & Claims

Software and Systems Modeling (SoSyM), Volume 14, Issue 2

Pages 597 - 621

https://doi.org/10.1007/s10270-013-0372-2

Published: 01 May 2015 Publication History

Abstract

In this paper, we propose a new model-sensitive search plan generation algorithm to speed up the process of graph pattern matching. This dynamic-programming-based algorithm, which is able to handle general n-ary constraints in an integrated manner, collects statistical data from the underlying EMF model and uses this information for optimization purposes. Additionally, the search plan generation algorithm itself and its runtime effects on the pattern matching engine have been evaluated by complexity analysis techniques and by quantitative performance measurements, respectively.

References

[1]

Anjorin, A., Varró, G., Schürr, A.: Complex attribute manipulation in TGGs with constraint-based programming techniques. In: Hermann, F., Voigtländer, J. (eds.) Proceedings of the 1st International Workshop on Bidirectional Transformations. Electronic Communications of the EASST, vol. 49, (March 2012)

[2]

Balogh, A., Varró, D.: Advanced model transformation language constructs in the VIATRA2 framework. In: Proceedings of the 21st ACM Symposium on Applied Computing. pp. 1280---1287. ACM Press, Dijon (April 2006)

[3]

Batz, G.V., Kroll, M., Geiß, R.: A first experimental evaluation of search plan driven graph pattern matching. In: Schürr, A., Nagl, M., Zündorf, A. (eds.) Proceedings of the 3rd International Symposium on the Applications of Graph Transformation with Industrial Relevance. LNCS, vol. 5088, pp. 471---486. Springer (2008)

[4]

Buchmann, T., Westfechtel, B., Winetzhammer, S.: The added value of programmed graph transformations--a case study from software configuration management. In: Schürr, A., Varró, D., Varró, G. (eds.) Proceedings of the 4th International Symposium on Applications and Graph Transformations with Industrial Relevance. LNCS, vol. 7233, pp. 198---209. Springer, Budapest (Oct 2012)

[5]

Byröd, M., Lennartson, B., Vahidi, A., Åkesson, K.: Efficient reachability analysis on modular discrete-event systems using binary decision diagrams. In: Proceedings of the 8th International Workshop on Discrete Event Systems. pp. 288---293. IEEE (2006)

[6]

Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: An improved algorithm for matching large graphs. In: Proceedings of the 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition. pp. 149---159 (May 2001)

[7]

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)

[8]

Efficient instance-level ontology validation by incremental model query techniques. http://viatra.inf.mit.bme.hu/publications/trainbenchmark. Accessed: 15/10/2012

[9]

Fischer, T., Niere, J., Torunski, L., Zündorf, A.: Story diagrams: a new graph rewrite language based on the unified modeling language. In: Engels, G., Rozenberg, G. (eds.) Proceedings of the 6th International Workshop on Theory and Application of Graph Transformation. LNCS, vol. 1764, pp. 296---309. Springer (1998)

[10]

Foggia, P., Sansone, C., Vento, M.: A performance comparison of five algorithms for graph isomorphism. In: Proceedings of the 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition. pp. 188---199 (May 2001)

[11]

Geiger, L., Schneider, C., Reckord, C.: Template- and model-based code generation for MDA-tools. In: Giese, H., Zündorf, A. (eds.) Proceedings of the 3rd International Fujaba Days. pp. 57---62 (2005), ftp://ftp.upb.de/doc/techreports/Informatik/tr-ri-05-259.pdf

[12]

Geiß, R., Batz, V., Grund, D., Hack, S., Szalkowski, A.M.: GrGen: a fast SPO-based graph rewriting tool. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L., Rozenberg, G. (eds.) Proceedings of the 3rd International Conference on Graph Transformation. LNCS, vol. 4178, pp. 383---397. Springer (2006)

[13]

Giese, H., Hildebrandt, S., Seibel, A.: Improved flexibility and scalability by interpreting story diagrams. In: Margaria, T., Padberg, J., Taentzer, G. (eds.) Proceedings of the 8th International Workshop on Graph Transformation and Visual Modeling Techniques. ECEASST, vol. 18 (2009)

[14]

Horváth, Á., Varró, G., Varró, D.: Generic search plans for matching advanced graph patterns. In: Ehrig, K., Giese, H. (eds.) Proceedings of the 6th International Workshop on Graph Transformation and Visual Modeling Techniques. Electronic Communications of the EASST, vol. 6. Braga, Portugal (March 2007)

[15]

Jouault, F., Kurtev, I.: Transforming models with ATL. In: Bézivin, J., Rumpe, B., Schürr, A., Tratt, L. (eds.) Proceedings of the International Workshop on Model Transformation in Practice. LNCS, vol. 3844, pp. 128---138. Springer (2005)

[16]

Lambers, L., Hildebrandt, S., Giese, H., Orejas, F.: Attribute handling for bidirectional model transformations: the triple graph grammar case. In: Hermann, F., Voigtländer, J. (eds.) Proceedings of the 1st International Workshop on Bidirectional Transformations. Electronic Communications of the EASST, vol. 49. Tallinn, Estonia (March 2012)

[17]

Lauder, M.: Incremental Model Synchronization with Precedence-Driven Triple Graph Grammars. Ph.D. thesis, Technische Universität Darmstadt (Feb 2013)

[18]

Le, W., Kementsietsidis, A., Duan, S., Li, F.: Scalable multi-query optimization for SPARQL. In: Gehrke, J., Ooi, B.C., Pitoura, E. (eds.) Proceedings of the 2012 IEEE 28th International Conference on Data Engineering. pp. 666---677. IEEE Computer Society, Arlington, Virginia (2012)

[19]

Lee, C., Shih, C.S., Chen, Y.H.: Optimizing large join queries using a graph-based approach. IEEE Trans. Knowl. Data Eng. 13(2), 298---315 (2001)

Digital Library

[20]

Meinel, C., Theobald, T.: Algorithms and Data Structures in VLSI Design: OBDD Foundations and Applications. Springer, Berlin (1998)

[21]

Moerkotte, G., Neumann, T.: Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products. In: Proceedings of the 32nd International Conference on Very Large Data Bases. pp. 930---941. VLDB Endowment, Seoul, Korea (2006)

[22]

Neumann, T., Weikum, G.: Scalable join processing on very large RDF graphs. In: Binnig, C., Dageville, B. (eds.) Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. pp. 627---640. ACM, Providence, Rhode Island (2009)

[23]

Özsu, M.T., Blakeley, J.A.: Query processing in object-oriented database systems. ACM Trans. Inf. Syst. 8, 387---430 (1994)

[24]

Rensink, A.: The GROOVE simulator: a tool for state space generation. In: Pfalz, J.L., Nagl, M., Böhlen, B. (eds.) Proceedings of the 2nd International Symposium on the Applications of Graph Transformations with Industrial Relevance. LNCS, vol. 3062, pp. 479---485. Springer (2004)

[25]

Roebuck, K.: Object-Relational Mapping: High-Impact Strategies--What You Need to Know: Definitions, Adoptions, Impact, Benefits, Maturity. Vendors, Lightning Source Incorporated (2011)

[26]

Rozenberg, G. (ed.): Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1: Foundations. World Scientific, Singapore (1997)

[27]

Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., Price, T.G.: Access path selection in a relational database management system. In: Bernstein, P.A. (ed.) Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data. pp. 23---34. ACM, Boston, Massachusetts (1979)

[28]

Stocker, M., Seaborne, A., Bernstein, A., Kiefer, C., Reynolds, D.: SPARQL basic graph pattern optimization using selectivity estimation. In: Ma, W.Y., Tomkins, A., Zhang, X. (eds.) Proceedings of the 17th International Conference on World Wide Web. pp. 595---604. ACM, Beijing, China (April 2008)

[29]

The MOGENTES project: http://www.mogentes.eu/

[30]

Ullmann, J.R.: An algorithm for subgraph isomorphism. J. ACM 23(1), 31---42 (1976)

Digital Library

[31]

Varró, G., Anjorin, A., Schürr, A.: Unification of compiled and interpreter-based pattern matching techniques. In: Tolvanen, J.P., Vallecillo, A. (eds.) Proceedings of the 8th European Conference on Modelling Foundations and Applications. Lecture Notes in Computer Science, vol. 7349, pp. 368---383. Springer, Lyngby (July 2012)

[32]

Varró, G., Deckwerth, F., Wieber, M., Schürr, A.: An algorithm for generating model-sensitive search plans for EMF models. In: Hu, Z., de Lara, J. (eds.) Proceedings of the 5th International Conference on Model Transformation. Lecture Notes in Computer Science, vol. 7307, pp. 224---239. Springer, Prague (May 2012)

[33]

Varró, G., Varró, D., Friedl, K.: Adaptive graph pattern matching for model transformations using model-sensitive search plans. In: Karsai, G., Taentzer, G. (eds.) Proceedings of International Workshop on Graph and Model Transformation. Electronic Notes in Theoretical Computer Science, vol. 152, pp. 191---205. Elsevier, Tallinn (Sep 2005)

[34]

Varró, G.: Advanced Techniques for the Implementation of Model Transformation Systems. Ph.D. thesis, Budapest University of Technology and Economics (April 2008)

[35]

Wickes, W.E.: Logic Design with Integrated Circuits. Wiley, London (1968)

[36]

Zündorf, A.: Graph pattern matching in PROGRES. In: Cuny, J., Ehrig, H., Engels, G., Rozenberg, G. (eds.) Proceedings 5th Int. Workshop on Graph Grammars and Their Application to Computer Science. LNCS, vol. 1073, pp. 454---468. Springer (1996)

Cited By

Búr MMarussy KMeyer BVarró D(2021)Worst-case Execution Time Calculation for Query-based Monitors by Witness GenerationACM Transactions on Embedded Computing Systems10.1145/347190420:6(1-36)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3471904
Groner RBeaucamp LTichy MBecker SSyriani ESahraoui H(2020)An exploratory study on performance engineering in model transformationsProceedings of the 23rd ACM/IEEE International Conference on Model Driven Engineering Languages and Systems10.1145/3365438.3410950(308-319)Online publication date: 16-Oct-2020
https://dl.acm.org/doi/10.1145/3365438.3410950
Búr MSzilágyi GVörös AVarró D(2020)Distributed graph queries over [email protected] for runtime monitoring of cyber-physical systemsInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-019-00531-522:1(79-102)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s10009-019-00531-5
Show More Cited By

Recommendations

An algorithm for generating model-sensitive search plans for EMF models
ICMT'12: Proceedings of the 5th international conference on Theory and Practice of Model Transformations

In this paper, we propose a new model-sensitive search plan generation algorithm to speed up the process of graph pattern matching. This dynamic programming based algorithm, which is able to handle general n-ary constraints in an integrated manner, ...
Adaptive Graph Pattern Matching for Model Transformations using Model-sensitive Search Plans

The current paper makes two contributions for the graph pattern matching problem of model transformation tools. First, model-sensitive search plan generation is proposed for pattern traversal (as an extension to traditional multiplicity and type ...
Generating Plans Using LRTA
BRACIS '13: Proceedings of the 2013 Brazilian Conference on Intelligent Systems

A new category of faster and efficiently planners has been used to solve planning problems, which use heuristic search algorithms to build their plans. One of the first successful planning systems to use this new approach was the Fast Forward (FF) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Software and Systems Modeling (SoSyM)

Software and Systems Modeling (SoSyM) Volume 14, Issue 2

May 2015

513 pages

ISSN:1619-1366

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer-Verlag Berlin Heidelberg.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 May 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Búr MMarussy KMeyer BVarró D(2021)Worst-case Execution Time Calculation for Query-based Monitors by Witness GenerationACM Transactions on Embedded Computing Systems10.1145/347190420:6(1-36)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3471904
Groner RBeaucamp LTichy MBecker SSyriani ESahraoui H(2020)An exploratory study on performance engineering in model transformationsProceedings of the 23rd ACM/IEEE International Conference on Model Driven Engineering Languages and Systems10.1145/3365438.3410950(308-319)Online publication date: 16-Oct-2020
https://dl.acm.org/doi/10.1145/3365438.3410950
Búr MSzilágyi GVörös AVarró D(2020)Distributed graph queries over [email protected] for runtime monitoring of cyber-physical systemsInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-019-00531-522:1(79-102)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s10009-019-00531-5
Groner RPretschner AVoss SBurgueño L(2019)User-centered performance engineering of model transformationsProceedings of the 22nd International Conference on Model Driven Engineering Languages and Systems Companion10.1109/MODELS-C.2019.00097(635-641)Online publication date: 15-Sep-2019
https://dl.acm.org/doi/10.1109/MODELS-C.2019.00097
Boronat AWąsowski APaige RHaugen Ø(2018)Expressive and Efficient Model Transformation with an Internal DSL of XtendProceedings of the 21th ACM/IEEE International Conference on Model Driven Engineering Languages and Systems10.1145/3239372.3239386(78-88)Online publication date: 14-Oct-2018
https://dl.acm.org/doi/10.1145/3239372.3239386
Groner RTichy MBecker SWolter KKnottenbelt Wvan Hoorn ANambiar MKoziolek H(2018)Towards Performance Engineering of Model TransformationCompanion of the 2018 ACM/SPEC International Conference on Performance Engineering10.1145/3185768.3186305(33-36)Online publication date: 2-Apr-2018
https://dl.acm.org/doi/10.1145/3185768.3186305
Szárnyas GIzsó BRáth IVarró D(2018)The Train BenchmarkSoftware and Systems Modeling (SoSyM)10.1007/s10270-016-0571-817:4(1365-1393)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10270-016-0571-8
Jukšs MVerbrugge CElaasar MVangheluwe H(2018)Scope in model transformationsSoftware and Systems Modeling (SoSyM)10.1007/s10270-016-0555-817:4(1227-1252)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10270-016-0555-8
Varró DBergmann GHegedüs ÁHorváth ÁRáth IUjhelyi Z(2016)Road to a reactive and incremental model transformation platformSoftware and Systems Modeling (SoSyM)10.1007/s10270-016-0530-415:3(609-629)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s10270-016-0530-4

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents