| 子图同构验证算法OES |
| |
| 引用本文： | 解春欣,汪卫.子图同构验证算法OES[J].计算机工程,2011,37(3):30-32. |
| |
| 作者姓名： | 解春欣 汪卫 |
| |
| 作者单位： | 复旦大学计算机科学技术学院,上海,200433 |
| |
| 摘 要： | 提出一种新的子图同构验证算法OES，采用逐条边验证的方法寻找子图同构映射，以确定查询图是否为某个数据图的子图，通过调整边的验证顺序，提高算法的执行效率。给出一种为查询图的边打分的方法，每条边的得分越低，表明其剪枝效率越高，按照分数由低到高的边序验证可以取得较好的验证效率。
|
| 关 键 词： | 子图查询 子图同构算法 查询优化 OES算法 |
OES:Subgraph Isomorphism Verification Algorithm |
| |
| XIE Chun-xin,WANG Wei.OES:Subgraph Isomorphism Verification Algorithm[J].Computer Engineering,2011,37(3):30-32. |
| |
| Authors: | XIE Chun-xin WANG Wei |
| |
| Affiliation: | (School of Computer Science,Fudan University,Shanghai 200433,China) |
| |
| 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. |
| |
| Keywords: | subgraph query subgraph isomorphism algorithm query optimization OES algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
|
