面向大规模知识图谱的分布式查询系统

• 作 者: 周华健
• 出 处: 华中科技大学
• 发表日期: 2020年01期
• 基金项目: 国家重点研发计划“制造全流程协同知识建模技术研究”；

知识图谱是描述真实世界中实体和概念以及它们之间联系的关系网络,利用知识图谱可以更好的查询复杂的关联信息,并且可以更精确的查出用户所需的信息。主流搜索引擎开始研究知识图谱并计划将知识图谱作为下一代搜索引擎的底层数据结构,现有的工作大多集中于分布式存储过程的数据结构设计和处理优化,但在负载均衡和图连接方面的研究仍需重大突破。面向大规模知识图谱的分布式查询系统应运而生。首先,设计了面向管理节点的抽象数据类和面向数据节点的数据实类,以实现管理节点连接策略选择与数据节点单机查询的并行。面向管理节点的抽象数据类不存储真正的数据,只存储数据节点的数据获取方法以减少数据流动。面向数据节点的数据实类将中间结果存储在内存之中,以减少I/O的时间消耗。抽象数据类与数据实类一一对应,抽象查询类通过合并、分裂和连接操作来控制数据节点的数据粒度,以实现执行节点之间的并行连接。当数据节点执行出错时,数据节点可根据抽象数据类的血缘关系来恢复数据。其次,创新性的引入图连接树来实现基于数据分布的分布式连接算法。图连接树是管理节点抽象数据类通过合并、分裂和连接操作得到最终结果抽象数据类的次序集合,执行节点依据图连接树来管理数据的流动并得到最终的查询结果。管理节点存储数据的统计索引以实现查询的结果数预测。基于结果数预测,以动态规划思想来创建图连接树以减少连接操作的执行次数,提高整体连接操作的效率。管理节点间隔性的统计某一时刻集群的负载情况。基于集群负载情况,以动态规划思将图连接树分解成图连接森林,每个执行节点根据自身负载情况选择最优图连接树以实现集群的负载均衡。然后,采用异步和非阻塞通信模式进行数据传输,将知识图谱中的主谓宾转换成固定长度编码以提高交互效率。最后,设计实现了基于数据分布的分布式查询系统,并对不同的数据提供支持。为验证基于数据分布的分布式连接算法的高效性,将传统的三种分布式图连接算法移植到基于数据分布的分布式查询系统进行对比测试,采用大规模数据集和国际标准分布式查询用例以提高测试的权威性。采用五种规模的集群和数据集来验证基于数据分布的查询系统的可扩展性。实验结果表明,基于数据分布的分布式图连接算法比传统分布式连接算法具有更高的并行性和更少的时间消耗,基于数据分布的分布式查询系统具有良好的可扩展性。