|
|||||
|
|
| 基于关系模型的子图同构检测算法设计与实现 | |
| 引用本文： | 刘波,房斌,张世勇,李直霖.基于关系模型的子图同构检测算法设计与实现[J].计算机工程,2011,37(11):62-63,66. |
| 作者姓名： | 刘波 房斌 张世勇 李直霖 |
| 作者单位： | 1. 重庆大学计算机学院,重庆,400044;重庆工商大学计算机科学与信息工程学院,重庆,400067;电子商务重庆市重点实验室,重庆,400067 2. 重庆大学计算机学院,重庆,400044 3. 重庆工商大学计算机科学与信息工程学院,重庆,400067 4. 煤炭科学研究总院重庆研究院,重庆,400037 |
| 摘 要： | 在图分解索引(GDI)算法的基础上，利用关系模型存储图的分解信息，采用B*树对子图结点度进行索引，由此提出一种新的子图同构检测算法——关系图分解索引(RGDI)。实验结果证明，与GDI相比，RGDI可节省更多存储空间，得到的候选集更准确，且子图同构检测效率更高。 |
| 关 键 词： | 图数据库 图分解索引算法 子图同构 B*树 关系模型 |
| 收稿时间： | 2011-02-21 |
Design and Implementation of Subgraph Isomorphism Detection Algorithm Based on Relational Model |
|
| LIU Bo,FANG Bin,ZHANG Shi-yong,LI Zhi-lin.Design and Implementation of Subgraph Isomorphism Detection Algorithm Based on Relational Model[J].Computer Engineering,2011,37(11):62-63,66. | |
| Authors: | LIU Bo FANG Bin ZHANG Shi-yong LI Zhi-lin |
| Affiliation: | 1.College of Computer Science,Chongqing University,Chongqing 400044,China;2.School of Computer Science and Information Engineering,Chongqing Technology and Business University,Chongqing 400067,China;3.Chongqing Key Laboratory of Electronic Commerce,Chongqing 400067,China;4.Chongqing Institute of Coal Science Research Institute,Chongqing 400037,China) |
| Abstract: | Based on Graph Decomposition Index（GDI） algorithm,by using relational model to store decomposition information of the graph and utilizing B＊ tree to index degree of node in graph,this paper proposes a new subgraph isomorphism algorithm named Relational Graph Decomposition Index（RGDI）.Experimental results show that compared with GDI,RGDI can save more storage space,get more precise candidate sets and has higher detection efficiency. |
| Keywords: | graph database Graph Decomposition Index（GDI） algorithm subgraph isomorphism B＊ tree relational model |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程》浏览原始摘要信息 | |
| 点击此处可从《计算机工程》下载全文 | |