扩展子图同构问题的优化算法_徐凯旋.pdfVIP

第37 卷 第19 期 计 算 机 工 程 2011 年10 月 Vol.37 No.19 Computer Engineering October 2011 ·软件技术与数据库· 文章编号：1000—3428(2011)19—0038—03 文献标识码：A 中图分类号：TN919.81 扩展子图同构问题的优化算法 徐凯旋，鲁道夫 (复旦大学计算机科学学院智能信息处理实验室，上海 201203) 摘 要：针对扩展子图的匹配问题，根据Ullmann 剪枝和QuickSI 的不同特性，提出优化处理距离信息的加边算法。根据Query 中各个顶 点到不同label 顶点的最短距离进行剪枝，采用动态加边算法减少加边的运算时间，能够处理规模不大的稀疏图。在AIDS 数据库上的实验 结果表明，在不同距离值的条件下，QuickSI 算法的平均运行速度比Ullmann 算法快一个数量级以上。 关键词：图数据库；AIDS 数据库；Ullmann 算法；扩展子图同构；动态加边算法 Optimized Algorithm of Extended Subgraph Isomorphism Problem XU Kai-xuan, Rudolf Fleischer (Intelligence Information Processing Lab, School of Computer Science, Fudan University, Shanghai 201203, China) 【Abstract 】This paper proposes an improved algorithm to solve extended subgraph isomorphism problem, that is to optimize the adding-edge procedure to deal with the distance information, according to the different characteristics of Ullmann and QuickSI. In the formal one, shortest distances for every node to each label in query are computed to cut branches, and in the latter one, it uses the dynamic BFS procedure to reduce the running time for adding edges. To give the comparison under different edge weight settings, it conducts series of experiments on AIDS database. Results suggest that the average performance of QuickSI algorithm is more than an order of magnitude faster. 【Key words 】graph database; AIDS database; Ullmann algorithm; extended subgraph isomorphism; dynamic adding-edge algorithm DOI: 10.3969/j.issn.1000-3428.2011.19.011 1 概述 2 问题表述和优化算法 子图同构问题在很多领域有着很多非常重要的应用。这