学位论文 > 优秀研究生学位论文题录展示

图数据库查询处理技术的研究

作　者: 张硕
导　师: 李建中
学　校: 哈尔滨工业大学
专　业: 计算机软件与理论
关键词: 超图查询概率top-k子图匹配查询图统计信息子图同构不确定图
分类号: TP311.13
类　型: 博士论文
年　份: 2010年
下　载: 324次
引　用: 0次
阅　读: 论文下载

内容摘要

作为一种通用的数据结构,图可以用来表示数据对象之间的复杂联系。例如:图可以表示化合物的分子结构,蛋白质交互网络,社会网络等。随着科学与工程领域中图数据的大量出现和累积,图数据管理已成为数据管理领域一个重要和热点研究的子领域。图数据库查询处理是其中最重要的研究分支之一,其对图相关的绝大部分处理和应用(例如:图挖掘、化学数据库PubChem)起着基础支撑作用。本文主要对图数据库中的查询处理技术进行深入研究,归纳总结了现有研究成果的主要思想和优缺点,提出了一些新的图数据库查询处理方法,主要研究成果如下:1.提出一种图数据库中高效处理超图包含查询的新方法。新方法综合的从图数据库的压缩组织、构造有效的特征索引以及基于压缩组织来处理查询三个方面着手考虑问题。(1)在图数据库的压缩组织方面,提出图数据库的有效组织方法,以提高整体查询处理效率。现有的采用过滤-验证机制的方法将图数据库中的图逐个的独立存放。提出方法将图数据库中图结构化的压缩组织起来。通过压缩组织方法,产生一个逻辑数据结构GPTree,其中记录了数据库中图的公共子图的信息。为了优化的构造GPTree,形式化定义了最优诱导子图选择问题;证明了其是一个NP难问题,并提出了一个近似比为2的近似算法。(2)在构造有效的特征索引方面,提出高效而不依赖于历史查询的子图索引特征生成方法,以及两种索引结构CRGraph和FGPForest。首先基于分析,给出索引特征的显著性度量。提出了找出所有显著性不小于用户需求的索引特征的方法,即精确索引特征生成方法。为了适应需要更加快速的生成索引的应用场景,提出了特征索引构造的一个近似方法。这两种方法都是基于图模式挖掘的方法。为了高效使用索引特征,对索引特征进行排序;并且基于理论分析给出了求解其最优排序的算法。(3)在基于压缩组织来处理查询方面,提出从多个图到一个图的子图同构检测的新方法,称为GPTreeTest。现有方法逐个的考察每个图对进行检测,新方法能够利用压缩组织中公共子图的信息,显著减少对多个图的子图同构检测的总时间。最后,在真实数据集和合成数据集上的实验结果表明,提出方法比目前最好方法高效1至2个数据量级。2.提出不确定图数据库上概率top-k子图匹配查询的新问题、以及一种查询处理方法。首先给出不确定图数据模型,结合现实需求提出概率top-k子图匹配查询问题。一个顶点的邻居子图是由其距离不大于给定阈值内的所有顶点和边构成的子图。基于图结构空间相关性的特点,以附带概率信息的邻居子图为基础,设计一种有效的索引结构NG-Index。NG-Index索引可以很容易实现于成熟的关系数据库中,具有强健壮性。提出一种高效的基于搜索树的算法来进行查询处理。其中运用了一种概率剪枝技术来提高性能。最后通过实验考察并证实提出方法具有良好的效率和可扩展性。3.提出结合概念分层的图统计信息定义以及查询处理方法。具体地说,给出了结合顶点关联的概念分层,根据用户指定的搜索兴趣来高效地计算数据图中统计信息的方法。首先提出一种结合概念分层的图统计分布表示。本文将用户搜索兴趣建模为概念图,并以用户概念图的子图匹配计数为基础来表示图统计信息。其次,为了高效计算此统计分布信息,设计了一种基于子图密度的索引结构并提出两阶段的计算方法: (1)先基于索引快速地去除数据图中的不相关边并将数据图打散划分为若干小尺寸的连通图;(2)再对这些连通小图分别计算统计信息,最后合并得出结果。在连通小图上计算统计信息的核心是概念图的子图匹配计数问题。文中针对这个子问题着重提出两种高效算法:前向计算算法和后向计算算法。这种在精确计算之前将数据大图快速打散为多个小图的分治思想是总体效率提升的关键所在。最后,在真实数据集上的实验结果表明所提出方法具有良好的效率和可扩展性。4.提出了一种较大尺寸的标签图子图同构检测方法及其应用方法。所提出的检测方法是一种基于搜索的方法。本文从标签图的特性出发,以标签信息和图拓扑结构相结合的方式来缩减搜索空间。首先,将标签按照出现的频率比转换为数值。然后,将标签信息与结构相结合,来构造多组细粒度的顶点不变量。顶点不变量是关于顶点的固有属性,其在同构映射下保持不变。借助于所构造的细粒度的顶点不变量,将标签信息沿图拓扑结构传播开来,并缩减匹配顶点候选集来减小搜索空间。再次,基于顶点不变量生成了细粒度的剪枝条件。由于结合标签信息和拓扑结构,这些条件具有更强的剪枝能力。另外,将提出检测方法中的技术细节应用到第2章提出的GPTree结构上,来显示其可用来优化已有方法的适用性。最后实验结果表明,提出方法具有良好的高效性,同时应用新技术的GPTreeTest*算法效率优于原始方法GPTreeTest。

全文目录

摘要  4-6
Abstract  6-15
插图  15-19
表格  19-21
算法  21-23
第1章绪论  23-40
  1.1 研究的目的和意义  23-25
  1.2 国内外研究现状  25-35
    1.2.1 图数据库查询处理  26-30
    1.2.2 图模式挖掘  30-32
    1.2.3 不确定图数据管理与挖掘  32-33
    1.2.4 图查询处理领域的其它研究工作  33-35
  1.3 本文的主要研究工作  35-38
    1.3.1 本文的主要研究问题  35-37
    1.3.2 本文的主要研究成果  37-38
  1.4 本文的章节安排  38-40
第2章超图查询处理  40-80
  2.1 引言  40-42
  2.2 相关工作  42-44
  2.3 预备知识  44-46
  2.4 问题定义  46-47
  2.5 超图查询处理  47-73
    2.5.1 图数据库压缩组织方式  47-59
    2.5.2 索引构建  59-67
    2.5.3 基于索引的查询处理方法  67-73
  2.6 实验结果及分析  73-78
    2.6.1 实验设置及数据集  73
    2.6.2 实验结果及分析  73-78
  2.7 本章小结  78-80
第3章不确定图数据库概率Top-k子图匹配查询处理  80-107
  3.1 引言  80-82
  3.2 相关工作  82-84
  3.3 问题定义  84-88
    3.3.1 不确定图数据库  84-88
    3.3.2 概率Top-k子图匹配查询  88
  3.4 不确定图数据库概率Top-k子图匹配查询处理  88-101
    3.4.1 子图匹配概率的计算  88-90
    3.4.2 索引构建  90-95
    3.4.3 基于索引的查询处理方法  95-101
  3.5 实验结果及分析  101-106
    3.5.1 实验设置及数据集  101-102
    3.5.2 实验结果及分析  102-106
  3.6 本章小结  106-107
第4章结合概念分层的图统计信息查询处理  107-128
  4.1 引言  107-109
  4.2 预备知识  109-110
  4.3 问题定义  110-113
    4.3.1 基本概念  110-111
    4.3.2 图统计分布信息表示  111-113
  4.4 图统计信息查询处理  113-121
    4.4.1 索引构建  113
    4.4.2 基于索引的两阶段处理方法  113-121
  4.5 实验结果及分析  121-127
    4.5.1 实验设置及数据集  121-122
    4.5.2 实验结果  122-127
  4.6 本章小结  127-128
第5章较大尺寸标签图子图同构查询处理及其应用  128-147
  5.1 引言  128-130
  5.2 问题定义  130-131
  5.3 标签图子图同构查询处理  131-143
    5.3.1 基于标签与结构相结合的SITL方法  131-137
    5.3.2 GPTree应用  137-143
  5.4 实验结果及分析  143-146
  5.5 本章小结  146-147
结论  147-150
参考文献  150-162
攻读博士学位期间发表的学术论文及其它成果  162-165
致谢  165-167
个人简历  167-169

相似论文

基于特征压缩方法的图同构算法及其在网络模体发现中的应用,TP301.6
不确定图上的近邻查询与近邻模式挖掘算法研究,TP311.13
图结构数据上的子图查询,TP301.6
基于图的数据挖掘算法研究,TP311.13
频繁子图挖掘算法及其在生物网络中的应用,TP311.13
图的控制参数的若干问题,O157.5
基于子图同构的晶体管级电路门级模型抽取的研究,TN431.2
用于图分类的频繁子结构挖掘算法研究,TP311.13
图数据查询技术的研究,TP311.13
海量多数据库集成系统的查询处理研究,TP311.13
海量数据压缩、操作和处理方法的研究,TP311.13
海量多数据库集成系统的Mediator和Wrapper机制的设计与实现,TP311.13
隐式用户兴趣挖掘的研究与实现,TP311.13
基于BAP的数据压缩、操作与查询处理系统的实现,TP311.13
医疗信息集成平台中DICOM中间件及访问控制模型的设计与实现,TP311.13
K-均值聚类算法的研究与改进,TP311.13
基于流形学习的数据降维技术研究,TP311.13
K-means聚类优化算法的研究,TP311.13
基于分治法的聚类方法研究,TP311.13
不完备信息系统的完备化及其上的知识获取,TP311.13
演化聚类算法及其应用研究,TP311.13