A First Experimental Evaluation of Search Plan Driven Graph Pattern Matching
A First Experimental Evaluation of Search Plan Driven Graph Pattern Matching
复制标题
搜索计划驱动的图模式匹配的首次实验评估
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Rubino Geiß
中科院分区：
文献类型：
--
作者：
G. V. Batz;Moritz Kroll;Rubino Geiß
与图模式匹配的域图变换（GT）包含一个np完全子任务。但是对于现实生活中的应用程序来说，图形模式匹配必须尽可能快地执行。搜索计划驱动的主机图敏感（也称为模型敏感）图模式匹配方法解决了这个问题。据我们所知，这种方法的实验评估尚未发表。我们使用Varro等人介绍的著名的GT基准以及编译器构造的示例进行了关于运行时性能的第一次实验。此外，我们还提出了一种改进的成本模型和搜索计划及其生成的启发式算法。
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 Varro 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.