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

《基于双索引的子图查询算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第1期计算机工程2015年1月VO1．41NO．1ComputerEngineeringJanuary2015·先进计算与数据处理·文章编号：1000．3428(2015)01．004405文献标识码：A中图分类号：TP391基于双索引的子图查询算法陆慧琳，黄博(复旦大学计算机科学与技术学院智能信息处理重点实验室，上海200433)摘要：传统的子图查询算法大多只在图数据库上进i彳一次挖掘算法，即在图数据库上建立稳定的数据库索引后将不再对索引进行更新。随着查询兴趣的改变或数据库的频繁更新，原有的数据库索引将不再能提供有用的信息来减少查询过程中候

2、选图的数量。为此，提出一种双索引的子图查询算法，同时在数据库和查询流上挖掘频繁子图并建立索引。子图查询和查询流索引的建立同步进行，即使查询兴趣改变，查询流索引也能自适应地更新索引信息来优化查询效率。针对数据库的频繁更新．查询流索引已提供实时的有效信息，数据库索引无需重新建立。实验结果表明，双索引的结合能有效提高查询子图的处珲效率。关键词：双索引；查询流索引；子图查询；频繁子图；图数据库；子图同构中文引用格式：陆慧琳，黄博．基于双索引的子图查询算法[J]．计算机工程，2015，41(1)：44_48．英文引用格式：LuHuilin，HuangBo．Su

3、bgraphQueryAlgorithmBasedonDualIndex[J]．ComputerEngineering，20154l(1)：44_48．SubgraphQueryAlgorithmBasedonDualIndexB【Abstract】Mosttraditionalsubgraphqueryalgorithmsonlyconductamine—at—oncealgorithmonthegraphdatabase．Thatis，afterestablishingastabledatabaseindex，theindexisnolonger

4、beupdated．Thiskindofalgorithmsmayencountersuchproblems：withthequeryinterestfrequentlychangingorthedatabasefrequentlyupdating，theoriginaldatabaseindexbecomesincreasinglyobsoleteandnolongerprovidesusefulinformationtOefectivelyreducethenumberofcandidategraphs．Basedonthisconsiderat

5、ion，thispaperproposesadualindexstructurewhichminesfrequentsubgraphsonthedatabaseandthequerystream，andestablishesindexonthem．Theprocessofsubgraphqueryandtheestablishmentofqueryindexaresimultaneous．Theycomplementeachother．Soevenifthequeryinterestchanges，thequerystreamindexcanbead

6、aptivelyupdatedtOoptimizethequeryperformance．Forthefrequentupdatesofdatabase，thedatabaseindexdoesnotneedtobere—built，becausethequerystreamindexprovidesusefulinformationinrealtime．Experimentalresultsshowthatthedualindeximprovestheprocessingefficiencyofsubgraphquery．【Keywords】dua

7、lindex；querystreamindex；subgraphquery；frequentsubgraph；graphdatabase；subgraphisomorphismDOI：10．3969／j．issn．1000—3428．2015．01．008减少查询过程中候选图的数量，从而缩短整个子图1概述查询所需的时间。图作为一种通用的数据结构可以用来表示各种文献[4]是最早针对子图查询问题的研究，它提复杂的数据，被广泛地应用于各个领域，包括化学、出以路径为特征建立索引；文献[5]提出采用树形结生物信息、软件工程、社交网络以及互联网等。构+部分图结构

8、作为索引；文献[6]同样采用r树+而对于图数据库的管理与传统的数据库有许多的不部分图，不过它采用了一种基于哈