作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2015, Vol. 41 ›› Issue (1): 44-48. doi: 10.3969/j.issn.1000-3428.2015.01.008

• 先进计算与数据处理 • 上一篇    下一篇

基于双索引的子图查询算法

陆慧琳,黄博   

  1. 复旦大学计算机科学与技术学院智能信息处理重点实验室,上海 200433
  • 收稿日期:2014-03-05 修回日期:2014-04-03 出版日期:2015-01-15 发布日期:2015-01-16
  • 作者简介:陆慧琳(1988-),女,硕士研究生,主研方向:数据库技术,数据挖掘;黄 博,硕士。

Subgraph Query Algorithm Based on Dual Index

LU Huilin,HUANG Bo   

  1. Key Lab of Intelligent Information Processing,School of Computer Science,Fudan University,Shanghai 200433,China
  • Received:2014-03-05 Revised:2014-04-03 Online:2015-01-15 Published:2015-01-16

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

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

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

中图分类号: