Design and Implementation of Improved Graph Decomposition Index Algorithm
Subgraph Isomorphism Detection is a basic operation in graph database, while Graph Decomposed Index (GDI) is a simple and effective algorithm for Subgraph Isomorphism Detection. However, if there are too many vertexes in a graph, the detection efficiency will be largely reduced. In allusion to this weakness of GDI, the paper put forward a new algorithm for subgraph isomorphism detection, called EGDI (Enhanced Graph Decomposed Index). The new algorithm is based on GDI, adopting B+ tree to index all vortexes in a subgraph. In addition, a new HASH function is also introduced to organize data of the subgraph. Consequently, candidate sets become unnecessary for the process of subgraph isomorphism detection and the detection efficiency is also improved. Demonstrated by relevant experiments, EGDI is superior to GDI in algorithm efficiency.
Graph Database Graph Decomposition Subgraph Isomorphism B+Ttree HASH
Bo Liu Bin Fang Shi Ying Kang Shi Yong Zhang Hong Hong Qing
College of Computer Science, Chongqing University, Chongqing, China Chongqing Key Laboratory of E College of Computer Science, Chongqing University, Chongqing, China Chongqing Key Laboratory of Electronic Commerce, Chongqing, China School of Computer Science and In School of Computer Science and Information Engineering, Chongqing Technology and Business University School of Computer Science and Information Engineering, Chongqing Technology and Business University
国际会议
太原
英文
452-455
2011-02-26（万方平台首次上网日期，不代表论文的发表时间）