检索
E-mail
RSS
作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (19): 38-40.doi: 10.3969/j.issn.1000-3428.2011.19.011

• 软件技术与数据库 • 上一篇    下一篇

扩展子图同构问题的优化算法

徐凯旋，鲁道夫   

  1. (复旦大学计算机科学学院智能信息处理实验室，上海 201203)
  • 收稿日期:2011-04-20 出版日期:2011-10-05 发布日期:2011-10-05
  • 作者简介:徐凯旋(1982－)，男，硕士研究生，主研方向：图像语义分析，固定参数可解算法；鲁道夫，教授
  • 基金项目:
    国家自然科学基金资助项目(60973026)；上海市教委重 点学科基金资助项目(B114)；上海市科学技术委员会基金资助项目(08DZ2271800, 09DZ2272800)

Optimized Algorithm of Extended Subgraph Isomorphism Problem

XU Kai-xuan, Rudolf Fleischer   

  1. (Intelligence Information Processing Lab, School of Computer Science, Fudan University, Shanghai 201203, China)
  • Received:2011-04-20 Online:2011-10-05 Published:2011-10-05

PDF

1772

被引次数

2

摘要： 针对扩展子图的匹配问题，根据Ullmann剪枝和QuickSI的不同特性，提出优化处理距离信息的加边算法。根据Query中各个顶点到不同label顶点的最短距离进行剪枝，采用动态加边算法减少加边的运算时间，能够处理规模不大的稀疏图。在AIDS数据库上的实验结果表明，在不同距离值的条件下，QuickSI算法的平均运行速度比Ullmann算法快一个数量级以上。

关键词: 图数据库, AIDS数据库, Ullmann算法, 扩展子图同构, 动态加边算法

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

中图分类号: