基于分类的图索引方法研究.pdf

《基于分类的图索引方法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：ＴＰ３１１密级：公开ＵＤＣ．举号：００４９：１２１４８７Ｗ乂南大掌硕古学化论文基于分类的图索引方法研究研究生姓名；白泼搂导师姓名：金远平教授申请学位级别工学硕±学科专业名称计算机应用技术论文提巧日期２０１５巧５月论义答辩日期２０１５年６月１日学位授予单位东南大学学位授予日期２０１５年６月日答辩委员会主席徐立臻评阅人吕津华院盲２０１５年６月ＲＥＳＥＡＲＣＨＯＮＣＬＡＳＳＩＦＩＣＡＴＩＯＮＢＡＳＥＤＧＲＡＰ

2、ＨＩＮＤＥＸＥＳＡＴｈｅｓｉｓＳｕｂｍｉｔｅｄ化ＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙＦｏｒｔｈｅＡｃａｄｅｍｉｃＤｅｒｅｅｏｆＭａｓｔｅｒｏｆＥｎｉｇｇｉｎｅｅｒｎｇＢＹＢａｉＪｕｎｌｏｕＳｕｅｒｖｉｓｅｄｂｐｙＪｉｎＹｕａｎｉｎｐｇＳｃｈｏｏｌｏｆＣｏｍｕｔｅｒＳｃｉｅｎｃｅ＆ＥｎｉｎｅｅｒｉｎｐｇｇＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙ，ＮａｎｊｉｎｇＣＨＩＮＡＪｕｎｅ２０１５东南大学学位论文独创性声明

3、本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研巧成果。尽我所知，除了文中特别加Ｗ标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料一。与我同工作的同志对本研巧所做的任何贡献均己在论文中作了明确的说明并表示了谢意。研究生签名：句辟日期：今东南大学学位论文使用授权声明东南大学、中国科学技术信息研充所、国家图书馆有权保留本人所送交学位论文的，可抖采用影印复印件和电子文档、缩印或其他

4、复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致，，可。除在保密期内的保密论文外允许论文被查阅和借阅Ｕ公布（包括电子信息形式刊登）论文的全部内容或中、英文摘要等部分内容。论文的公布（包括Ｗ电子信息形式刊登）授权东南大学研巧生院办理。＇、研巧生签名：Ｖ４乏导师签名：：、纽＞、！Ｖ＿日期［摘要巧要随着图结构在复杂数据建模方面的广泛应用，图数据库技术得到了快速发展。如何一，从图数据库中快速检索数据己经成为个研究热点。在图查询中子图匹配查询和相似性查询是两种重要

5、的查询方式，。子图匹配查询是指返回数据库中包含查询图的图集合而相似性查询是返回数据库中与查询图相似的图集合。处理子图匹配查询和相似性查询时，分别需要进行子图同构验证和图相似度计算，但子图同构验证和图相似度计算己经＂被证明是ＮＰ难题。为了快速有效地返回图查询的结果，目前主要采用分类过滤＋验＂证两阶段处理机制。在这种机制中，首先预定义分类过滤规则，将图数据库分类，然后提取查询图特征，找到结果可能出现的类别，从而生成规模较小的候选集，最后对候选集进行子图同构验证或者图相似度计算得到最终的

6、结果集。其中，人们可Ｗ根据分类过滤规则构造合适的圓索引来提高查询效率。一现有的用于处理子图匹配查询的图索引方法中，般都是在查询前离线建立图索引，而忽视了查询图序列在时间上的相关性，容易出现冗余查巧Ｉ；已有的相似性查询的图索引方法主要集中在减少相似度的计算时间一，而并没有提出种缩小候选集规模的方法，仍需扫描整个数据库才能得到结果集。－－针对Ｗ上子图匹配查询问题，本文提出了种双索引的方法：首先。其主要思想是ｄｅｘ采用传统方法，基于图数据库离线建立图索引ＤＩｎｄｅｘＤａｔａｂａｓｅＩ

7、ｎ然后在查询过程（；）中，在线实时建立图索哥战１１３防脚５１〇１７１１１（１６乂）。出１１（１６乂中存放的是根据査询热度得到一的组频繁查询结构。泣样当某些图被重复査询时，可Ｗ首先捜索Ｈｌｎｄｅｘ，如果搜索成功，即可直接得到结果集，从而避免子图同构验证：如果搜索失败，则可按照传统方法搜索基于图数据库建立的索引Ｄｌｎｄｅｘ，得到候选窠。一为了缩小相似性查询问题中候选图的规模，本文提出了种多层过滤方法，并针对于不同的过滤层，分别提出了相适应的索引结构。首先将查询国的规模信息和项点标签

8、信息与图数据库中的图进行比较，将高偏差的图剔除；然后利用本文提出的基于子图向一量异或乘积的计算方法得到个有序集合，使得可能满足查询要求的图聚集在该集合的一前半部分，；之后本文采用类似二分査找的方式，通过计算映射距离动态调整得到个合适的下标值？，使得可能满足要求的酉都出现在该下标的左侧，这样就可（＾１将该下标左侧的图直接加入到候选集；为了提高结果集的查全率，有序集合中出现在下标右侧的图也有一部分被选入候选集