Subgraph Query Algorithm Based on Dual Index
LU Hui-li · Jisuanji gongcheng · 2015
Most traditional subgraph query algorithms only conduct a mine-at-once algorithm on the graph database.That is,after establishing a stable database index,the index is no longer be updated. This kind of algorithms may encounter such problems:with the query interest frequently changing or the database frequently updating,the original database index becomes increasingly obsolete and no longer provides useful information to effectively reduce the number of candidate graphs. Based on this consideration,this paper proposes a dual index structure which mines frequent subgraphs on the database and the query stream,and establishes index on them. The process of subgraph query and the establishment of query index are simultaneous. They complement each other. So even if the query interest changes,the query stream index can be adaptively updated to optimize the query performance. For the frequent updates of database,the database index doesnot need to be re-built,because the query stream index provides useful information in real time.Experimental results show that the dual index improves the processing efficiency of subgraph query.