Universität Karlsruhe
A First Experimental Evaluation of Search Plan Driven Graph Pattern Matching

Conference Article

[BKG:07]Gernot Veit Batz, Moritz Kroll, Rubino Geiß, A First Experimental Evaluation of Search Plan Driven Graph Pattern Matching, A. Schürr and M. Nagl and A. Zündorf (Ed.), Proc. 3rd Intl. Workshop on Applications of Graph Transformation with Industrial Relevance (AGTIVE '07), Springer, 2008 (http://www.springerlink.com/content/105633/).

Abstract

With graph pattern matching the field of graph transformation (GT) includes an NP-complete subtask. But for real-life applications it is essential that graph pattern matching is performed as fast as possible. This challenge has been attacked by the approach of search plan driven, host-graph-sensitive (also known as model-sensitive) graph pattern matching. To our knowledge no experimental evaluation of this approach has been published yet. We performed first experiments regarding the runtime performance using the well-known GT benchmark introduced by Varró et al. as well as an example from compiler construction. Moreover we present an improved cost model and heuristics for search plans and their generation.

[Generate bibTeX entry]

 

[Download]

Authors

Alumni
Dr. Rubino Geiß
Former Students
Gernot Veit Batz
Moritz Kroll
Login
Links