摘要： 在图分解索引(GDI)算法的基础上，利用关系模型存储图的分解信息，采用B*树对子图结点度进行索引，由此提出一种新的子图同构检测算法——关系图分解索引(RGDI)。实验结果证明，与GDI相比，RGDI可节省更多存储空间，得到的候选集更准确，且子图同构检测效率更高。
关键词:
图数据库,
图分解索引算法,
子图同构,
B*树,
关系模型
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.
Key words:
graph database,
Graph Decomposition Index(GDI) algorithm,
subgraph isomorphism,
B* tree,
relational model
中图分类号:
刘波, 房斌, 张世勇, 李直霖. 基于关系模型的子图同构检测算法设计与实现[J]. 计算机工程, 2011, 37(11): 62-63,66.
LIU Bei, 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.