大规模图数据库的相似性搜索算法研究

论文摘要

图作为强大的数据模型,不仅能够描述目标物体的属性,还能描述各个组成之间的结构关系,已经被成功地应用到许多领域中,包含生物信息学,计算机视觉,软件工程和社交网络等。另外一方面,随着信息技术的快速发展,可获得的图数据急剧增加,有效的图管理和查询变得越来越重要。相比于图数据库中的精确搜索,图相似性搜索可以提供鲁棒的解决方案,也就是说它支持容错和允许搜索不精确定义的模式。鉴于图编辑距离（Graph edit distance,GED）的优良特性:适用于任意类型的图和能够精确地捕捉图之间的结构和标签差异,本文考虑了基于GED度量的图相似性搜索问题。具体来讲,给定查询图Q和阈值τ,在图数据库D中找到所有与Q编辑距离小于或等于τ的图。由于GED计算是NP-hard问题,目前已有的方法都基于“过滤–验证”框架。在过滤阶段,设计不同的GED下界过滤那些肯定不满足阈值条件的图;这个阶段通过特定的索引结构高效地完成。在验证阶段利用精确的GED计算方法验证剩余的图。针对已有索引方法的不足（松弛的GED下界,过大的索引空间和有限的可扩展性）和GED计算方法的缺点（巨大的搜索空间,过量的内存消耗和许多昂贵的回溯）,本文提出了新的索引结构和GED计算方法,以提高图相似性搜索的性能。具体工作概括为下面四个部分:第一部分研究了解决图相似性搜索的外存索引结构。针对现有索引方法在处理大规模图数据库时具有有限的可扩展性,本文提出了一种基于q-gram表示的外存索引框架,它能够处理超大规模的图数据库。具体而言,将q-gram计数过滤器转变为稀疏矩阵向量乘（Sparse matrix-vector multiplication,SpMV）问题,并提出了基于混合布局的q-gram矩阵索引,以实现有效的查询处理。同时,将每个图转变为vertex-edge 2D空间的点,并将全局计数过滤器转变为2D查询矩形来提高查询性能;这允许只在缩小的查询区域中执行搜索,从而显著地减少查询I/O次数。在真实数据集上的实验结果表明所提外存索引能够处理包含2500万个化合物的超大数据集,并比基于q-gram的外存倒排索引需要更少的查询I/O次数。第二部分研究了解决图相似性搜索的简明索引结构。鉴于现有内存索引方法的过滤能力有限和索引空间过大的问题,本文提出了一种简明的q-gram树索引,它结合了简明数据结构和混合编码,以最小的内存空间使用来提高查询性能。具体来说,所提简明q-gram树的索引大小只有主流索引大小的5%–15%,但同时在测试数据集上实现了几倍的查询加速。此外,还提出了两个有效的GED下界（即,q-gram计数下界和度序列下界）和一种下界提升技术,以获得尽可能小的候选集。在真实和模拟数据集上的实验结果表明,所提简明q-gram树在索引大小和查询性能方面都优于主流索引方法。据我们所知,该索引是第一个能够处理包含2500万个化合物的超大数据集的内存索引。第三部分研究了GED的高效计算方法。观察到已有GED计算方法具有若干缺点:巨大的搜索空间,过量的内存消耗和许多昂贵的回溯调用,本文呈现了一种新颖的基于顶点映射的GED计算方法。该方法能够识别无效和冗余映射,从而在缩小的搜索空间中计算GED。此外,采用了波束堆栈搜索（beam-stack search）,并结合了两种专门设计的启发式方法来提高GED计算,实现了内存利用和回溯调用之间的均衡。在真实和模拟数据集上的实验结果表明,所提方法在稀疏和稠密图上都优于主流GED计算方法。此外,还扩展了该方法以解决图相似性搜索问题。实验结果表明,扩展后的方法比已有的图相似性搜索方法快几十倍。第四部分研究了GED的近似计算方法。考虑到GED计算的NP-hard困难性限制了其在很多领域中的应用,本文提出了一种任何时间算法（anytime algorithm）近似计算GED。该近似算法将运行时间作为参数从而输出一系列改进的GED次最优解（suboptimal solution）,以满足不同的运行时间需求。具体而言,提出了一种基于邻居偏差的贪心匹配方法,它能够在二次运行时间内快速地得到GED的初始次最优解;然后,采用结合了更有效的启发式估计的树搜索方法来提高所获得GED次最优解。该启发式函数基于扩展的分支编辑距离,理论上能够产生比标签编辑距离更加紧确的GED下界。在大的和小的运行时间设置下,相比于主流的GED近似算法,所提任何时间算法都能实现最小的偏差。

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 研究问题与现状
•     1.2.1 研究问题
•     1.2.2 研究现状
•   1.3 本文的主要工作
•   1.4 本文的章节安排
• 第二章 支持图相似性搜索的外存索引结构
•   2.1 引言
•   2.2 整体框架
•     2.2.1 框架
•     2.2.2 预处理
•   2.3 矩阵索引
•     2.3.1 计数过滤器
•     2.3.2 索引结构
•   2.4 查询处理
•     2.4.1 列优先布局
•     2.4.2 混合布局
•     2.4.3 查询算法
•   2.5 实验结果与分析
•     2.5.1 实验数据与设定
•     2.5.2 预处理评价
•     2.5.3 混合布局评价
•     2.5.4 与内存方法对比
•     2.5.5 与外存方法对比
•   2.6 本章小结
• 第三章 支持图相似性搜索的简明索引结构
•   3.1 引言
•   3.2 过滤原理
•     3.2.1 计数下界
•     3.2.2 度序列下界
•     3.2.3 提升技术
•   3.3 简明索引结构
•     3.3.1 树结构
•     3.3.2 简明表示
•     3.3.3 随机访问
•     3.3.4 查询算法
•   3.4 开销分析
•     3.4.1 存储开销估计
•     3.4.2 查询开销估计
•   3.5 实验结果与评价
•     3.5.1 实验数据与设定
•     3.5.2 简明表示评价
•     3.5.3 过滤器评价
•     3.5.4 与主流方法对比
•     3.5.5 扩展性评价
•   3.6 本章小结
• 第四章 一种高效的图编辑距离计算方法
•   4.1 引言
•   4.2 基础知识
•     4.2.1 图映射
•     4.2.2 基于顶点映射的图编辑距离计算方法
•   4.3 创建缩小的搜索空间
•     4.3.1 识别无效映射
•     4.3.2 识别冗余映射
•     4.3.3 生成后继结点
•     4.3.4 搜索空间分析
•   4.4 波束堆栈搜索
•     4.4.1 数据结构
•     4.4.2 搜索算法
•   4.5 搜索空间剪枝
•     4.5.1 启发式函数
•     4.5.2 顶点排序
•   4.6 实验结果与分析
•     4.6.1 数据集与设定
•     4.6.2 与已有的方法对比
•     4.6.3 评价优化技术
•   4.7 扩展支持图相似性搜索
•     4.7.1 扩展方法
•     4.7.2 在图相似性搜索上的表现
•   4.8 本章小结
• 第五章 一种近似图编辑距离计算的任何时间算法
•   5.1 引言
•   5.2 符号定义
•   5.3 基于邻居偏差的贪心匹配方法
•     5.3.1 代价矩阵
•     5.3.2 算法过程
•   5.4 通过树搜索算法求精
•     5.4.1 任何时间算法
•     5.4.2 启发式代价估计
•   5.5 实验结果与分析
•     5.5.1 数据集与设定
•     5.5.2 评价指标
•     5.5.3 实验结果
•   5.6 本章小结
• 第六章 结论与展望
•   6.1 结论
•   6.2 展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 博士论文

作者: 陈晓阳

导师: 霍红卫

关键词: 图编辑距离,图相似性搜索,外存索引,简明索引,波束堆栈搜索,任何时间算法

来源: 西安电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西安电子科技大学

分类号: O157.5

DOI: 10.27389/d.cnki.gxadu.2019.000097

总页数: 136

文件大小: 3226K

下载量: 80