面向大规模知识图谱的分布式查询技术研究

摘要

随着大数据时代的到来，人们所采集的数据量已达到ZB级规模。为了精确查询数据，越来越多的搜索引擎采用知识图谱作为底层数据支撑。知识图谱是描述现实世界中地点、人物、城市、电影等事物以及事物间联系的关系网络。利用知识图谱，搜索引擎可挖掘事物之间的内在联系，更准确地查找用户所需的信息。目前知识图谱中的数据主要从Wikipedia等知识百科中自动采集，存在大量未经验证的信息，导致知识图谱呈现出噪声数据多且数据规模大的特征，这些特征使得用户难以快速获取满意的查询结果。针对以上特征，如何实现快速高效的知识图谱查询是当前学术界和工业界亟待解决的问题。
　　现有工作通常将知识图谱查询建模成子图匹配问题，并已取得一定进展，但仍存在诸多不足。首先，现有查询模型大多要求查询结果与用户查询精确匹配，但是由于知识图谱存在噪声数据，这些模型会遗漏用户感兴趣的查询结果，存在可用性差的问题。其次，为了加快查询速度，现有查询算法普遍采用图索引技术，但是知识图谱的数据规模大，为其建立图索引需耗费高昂的时间和空间开销。最后，由于知识图谱规模庞大，所以需要采用分布式的方式实现查询过程，然而现有的分布式图数据处理平台未针对知识图谱查询的执行过程进行优化，存在执行效率低下的问题。因此，需设计新型的知识图谱查询模型、算法和计算平台以应对以上挑战。
　　本文针对知识图谱噪声数据多、数据规模大的特征，分别从知识图谱查询模型、分布式查询算法、分布式查询执行优化三个层面对知识图谱查询问题展开研究，旨在提供快速高效的新型分布式查询技术。第一，提出一种面向知识图谱的查询模型，基于模糊匹配的思想屏蔽噪声数据，始终保证返回满意的查询结果。第二，基于本文所提的查询模型，设计一种免索引的分布式查询算法，通过新型的限界技术优化查询时间，利用分布式环境的计算能力加快查询速度，达到快速响应查询请求的目的。第三，在分布式图数据处理平台上，分别从作业调度和数据存储两个方面优化分布式知识图谱查询的执行效率，减少数据I/O的开销，进一步缩短查询的整体完成时间。在理论研究的基础上，设计与实现面向大规模知识图谱的搜索引擎原型系统，部署面向学术文献知识图谱的查询应用，以验证本文的理论成果的有效性。
　　综上所述，本文针对知识图谱的两个特征，提出快速高效的分布式查询技术，保证用户可以快速获取满意的查询结果，为下一代搜索引擎提供行之有效的解决方案。随着知识图谱的不断普及，本文的研究成果将应用于商业、金融、生命科学等诸多领域，为商业决策、金融分析、生物制药等应用提供有效的数据查询支持，具有重大的社会意义。

目录

声明

摘要

插图目录

表格目录

缩略词表

第1章 绪论

1．1 研究背景

1．2 现有解决方法概述

1．2．1 经典的子图匹配算法

1．2．2 与知识图谱相关的查询算法

1．2．3 分布式图数据处理技术

1．3 存在问题与研究思路

1．4 研究目标与内容

1．4．1 研究目标

1．4．2 研究内容

1．5 论文组织

第2章 研究现状

2．1 引言

2．2 图查询技术研究现状

2．3 知识图谱查询研究现状

2．4 分布式大数据处理研究现状

2．5 研究现状总结

第3章 面向知识图谱的Top-k查询模型

3．1 引言

3．2 Top-k子图近似匹配问题

3．2．1 预备知识

3．2．2 近似度的衡量标准

3．3 模型的求解框架

3．3．1 两阶段的求解框架

3．3．2 阶段一：寻找Top-k*候选顶点

3．3．3 阶段二：寻找Top-k图嵌入

3．4 实验与分析

3．4．1 环境与参数设置

3．4．2 查询模型的有效性

3．4．3 与现有算法比较

3．4．4 k*的取值对查询性能的影响

3．5 小结

第4章 基于限界技术的分布式查询算法

4．1 引言

4．2 面向知识图谱查询的限界技术

4．2．1 限界技术概述

4．2．2 关联分值的上下界

4．2．3 算法终止条件

4．2．4 上下界的计算方法

4．2．5 算法正确性分析

4．3 分布式图查询算法的具体实现

4．3．1 实现方案概述

4．3．2 分布式的上下界计算方法

4．3．3 分布式的终止条件检查方法

4．4 实验与分析

4．4．1 运行环境与参数设置

4．4．2 与现有算法的比较

4．4．3 算法的执行性能

4．4．4 算法的可扩展性

4．5 小结

第5章 分布式图查询执行优化技术

5．1 引言

5．2 查询作业调度优化

5．2．1 延迟调度算法及其存在问题

5．2．2 面向图查询的延迟调度算法

5．2．3 数据本地性驱动的图查询任务指派

5．2．4 数据中心负载感知机制

5．2．5 延迟时间自适应调整机制

5．3 数据存储结构优化

5．3．1 数据共享技术

5．3．2 数据存储格式

5．4 实验与结果分析

5．4．1 运行环境与参数设置

5．4．2 调度算法的自适应性

5．4．3 作业的数据本地性

5．4．4 调度算法对查询时间的影响

5．4．5 存储结构对查询时间的影响

5．5 小结

第6章 面向知识图谱的搜索引擎原型系统

6．1 引言

6．2 GStar的总体设计

6．3 GStar功能模块设计与实现

6．3．1 离线数据处理子系统

6．3．2 在线分布式查询子系统

6．4 GStar系统部署与性能测试

6．4．1 GStar的实际部署

6．4．2 DBLP知识图谱和查询用例

6．4．3 GStar功能和性能测试

6．5 小结

第7章 总结与展望

7．1 论文总结

7．2 下一步研究方向

参考文献

致谢

攻读博士期间论文发表情况

攻读博士期间参与的科研项目

作者简介