基于关系模型的子图同构检测算法设计与实现  

Design and Implementation of Subgraph Isomorphism Detection Algorithm Based on Relational Model

作　　者：刘波[1,2,3] 房斌[1] 张世勇[2] 李直霖[4] 

机构地区：[1]重庆大学计算机学院,重庆400044 [2]重庆工商大学计算机科学与信息工程学院,重庆400067 [3]电子商务重庆市重点实验室,重庆400067 [4]煤炭科学研究总院重庆研究院,重庆400037

出　　处：《计算机工程》2011年第11期62-63,66,共3页Computer Engineering

基　　金：重庆市教委基金资助项目"农村管理与服务信息数据库研究与设计项目"(KJ080712)

摘　　要：在图分解索引(GDI)算法的基础上,利用关系模型存储图的分解信息,采用B*树对子图结点度进行索引,由此提出一种新的子图同构检测算法——关系图分解索引(RGDI)。实验结果证明,与GDI相比,RGDI可节省更多存储空间,得到的候选集更准确,且子图同构检测效率更高。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.

关 键 词：图数据库 图分解索引算法 子图同构 B＊树 关系模型 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]