摘要： 传统的子图查询算法大多只在图数据库上进行一次挖掘算法,即在图数据库上建立稳定的数据库索引后将不再对索引进行更新。随着查询兴趣的改变或数据库的频繁更新,原有的数据库索引将不再能提供有用的信息来减少查询过程中候选图的数量。为此,提出一种双索引的子图查询算法,同时在数据库和查询流上挖掘频繁子图并建立索引。子图查询和查询流索引的建立同步进行,即使查询兴趣改变,查询流索引也能自适应地更新索引信息来优化查询效率。针对数据库的频繁更新,查询流索引已提供实时的有效信息,数据库索引无需重新建立。实验结果表明,双索引的结合能有效提高查询子图的处理效率。

关键词: 双索引, 查询流索引, 子图查询, 频繁子图, 图数据库, 子图同构

Abstract: 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.

Key words: dual index, query stream index, subgraph query, frequent subgraph, graph database, subgraph isomorphism

中图分类号: 

• TP391