摘要： 针对扩展子图的匹配问题，根据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
中图分类号:
徐凯旋, 鲁道夫. 扩展子图同构问题的优化算法[J]. 计算机工程, 2011, 37(19): 38-40.
XU Kai-Xuan, LU Dao-Fu. Optimized Algorithm of Extended Subgraph Isomorphism Problem[J]. Computer Engineering, 2011, 37(19): 38-40.