图数据库中多子图匹配查询算法研究.pdf

《图数据库中多子图匹配查询算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图数据库中多子图匹配查询算法研究EfficientlyProcessingMultipleSubgraphMatchingQueriesinGraphDatabase黄博2012年4片指导小组成员名单周水庚教授复旦大学硕士学位论文目录目录1Abstract2第一章绪论31.1研究背景31.1.1图数据库简介31.1.2图匹配问题71.2问题描述81.3本文工作及结构9第二章图数据库查询研究现状112.1H构检测1129丨叫数彳子网办询2.2.1单-大图2.2.2人规模数椐库2.3(?编码第三章基于双重索引的多子图查询算法3.1概念与

2、定义3.1.1多子图叩配的饩洵序列..3.1.2子项3.1.3吋间戳3.2双重索引结构3.2.1数据库索引3.2.2查询索引3.2.3查询索引的优化复旦大学硕士学位论文3.3查询处理303.4索引维护323.5实验结果及分析333.5.1实验环境333.5.2AIDS数据集343.5.3模拟数据集363.6小结39第四章总结与展望41参考文献43猶48发表学术论文49ii复旦大学硕士学位论文摘要摘要图数据库是一种以图论为理论基础，描述并存储图中节点及其之间的关系的特定数据库。图数据库在处理大规模复杂、半结构化或无结构

3、数据时具有独特的优势，是数据库领域的热门研究课题。子图匹配作为图数据库的一个基本问题得到了学术界广泛关注，但现有算法大多以单个查询作为研究对象并进行优化。随着图数据库在社交网络、生物信息等领域的广泛应用，多查询处理成为图数据库的一个重要研究方向。本文研宄多子图匹配查询问题，针对图数据库和查询序列两种数据源，提出一种双重索引结构。一方面基于数据库的频繁子项建立数据库索引，另一方面基于查询序列的子图建立查询索引，并利丨H子项的包含关系建立两种索引的关联，将一段时间的查洵子图及匹配信息存储在查询索引中，进而利用历史查询中分步子图，提高结构相似的査询处理速度。该方法结合

4、图的编码技术禾11存储映射技术，支持索引的快速随机访问，其杏询索引结构能够快速更新，并使用双A检索的方法快速查找匹配集合。通过实验和现奋的经典算法进行比较,验iir.J'AaJ-k‘111:?Jrili'j)iJ'i-i-.o关键词：图数据库、多子图匹配查洵、双重索引中图分类号：TP3111复旦大学硕士学位论文AbstractAbstractGraphdatabaseisanovelformofstoragewhichisbasedongraphtheory,de-scriV)osandstoresclifFcTontkindsofdatabyusingnod

5、es,edgesandtheirattributes.Graphdatabasehasspecialadvantagesonlarge,complex,semi-structureclorun?structureddata,andisahotresearchtopicindatabasefield.Asabasicproblemingraphdatabase,subgraphmatchinghasdrewscholars'attention,buttheex?istingalgorithmsarefocusonoptimizingthesinglequery.W

6、ithwidespreaduseofthegraphdatabaseinthefieldofsocialnetworks,andbiologicalinformation,multi-queryprocessingbecomesanimportantresearchingraphdatabase.Thispaperfocusesonprocessingmultiplesubgraphmatchingqiu、ri(、s.Tlierearetwokindsof(latasources:oneisgraphdatabase,theotherisquerystream,

7、so\cproposeadualindexthatdatabaseindexisbuiltonfrequentfragments,andqueiyindexisbuiltonfragmentsincjuorvstream,bhidtwoindicesbyfragments'inclusionrelationship,andstore.sonicusefulinforniation(quones.matcliiiigsetsand(jiiJinit.YV。11vujiiiternu'cliatc1K、sult>inquriyu,impiou1theproces

8、singwhichque