Abstract: This paper proposes a novel subgraph isomorphism verification algorithm named OES, which tries to find a subgraph isomorphism map by searching edge by edge in order to check whether a query graph is contained in some data graphs, and it can raise the verification efficiency by adjusting the edge order. A grading method for edges in query graph is provided, in which the lower score an edge gets, the higher pruning efficiency it can gain. So that good efficiency can be gained by verifying the edges in the order from higher grades to lower grades.

Key words: subgraph query, subgraph isomorphism algorithm, query optimization, OES algorithm

摘要： 提出一种新的子图同构验证算法OES，采用逐条边验证的方法寻找子图同构映射，以确定查询图是否为某个数据图的子图，通过调整边的验证顺序，提高算法的执行效率。给出一种为查询图的边打分的方法，每条边的得分越低，表明其剪枝效率越高，按照分数由低到高的边序验证可以取得较好的验证效率。

关键词: 子图查询, 子图同构算法, 查询优化, OES算法

CLC Number: 

• TP311.13