Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Software and Systems Modeling
Erschienen in: Software and Systems Modeling 2/2015

01.05.2015 | Special Section Paper

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

verfasst von: Gergely Varró, Frederik Deckwerth, Martin Wieber, Andy Schürr

Erschienen in: Software and Systems Modeling | Ausgabe 2/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.
Vorheriger Artikel Constraint-driven modeling through transformation
Nächster Artikel Specification-driven model transformation testing

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
By using caching mechanisms, the search plan generation algorithm can be executed in a just-in-time manner.
 
2
Note that past and present check operations need not be stored as they will be immediately processed by the algorithm.
 
3
The runtime value is an average of 20 wall clock time measurements performed on a computer with 1.57 GHz Intel Core2 Duo CPU and 2.96 GB RAM. Windows XP Professional SP 3 and Java 1.7 served as the underlying operating system and virtual machine, respectively.
 
4
This means that the execution of the optimal search plan does not necessarily result in the traversal of the smallest state space.
 
Literatur
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)MATH
8.
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.
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)
20.
Meinel, C., Theobald, T.: Algorithms and Data Structures in VLSI Design: OBDD Foundations and Applications. Springer, Berlin (1998)CrossRef
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.
30.
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)MATH
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)
Metadaten
Titel
An algorithm for generating model-sensitive search plans for pattern matching on EMF models
verfasst von
Gergely Varró
Frederik Deckwerth
Martin Wieber
Andy Schürr
Publikationsdatum
01.05.2015
Verlag
Springer Berlin Heidelberg
Erschienen in
Software and Systems Modeling / Ausgabe 2/2015
Print ISSN: 1619-1366
Elektronische ISSN: 1619-1374
DOI
https://doi.org/10.1007/s10270-013-0372-2

Weitere Artikel der Ausgabe 2/2015

Software and Systems Modeling 2/2015 Zur Ausgabe

Regular Paper

VPML: an approach to detect design patterns of MOF-based modeling languages

Editorial

In memory of Robert B. France, Co-Founder and Editor-in-Chief of SoSyM from 1999 to 2015

Regular Paper

A survey of approaches for verifying model transformations

Special Section Paper

Enhancing classic transformation languages to support multi-level modeling

Regular Paper

Mashup of metalanguages and its implementation in the Kermeta language workbench

Special Section Paper

Recent and simple algorithms for Petri nets

Premium Partner

    Bildnachweise