基于子图近似匹配的海量知识图谱分布式查询技术研究

Knowledge graphs, which are massive networks containing real-world entities and the entities’ relationships, are commonly used by the next-generation search engines. The knowledge graphs are massive, incomplete and noisy in nature, so it is quite challenging to effectively and efficiently answer knowledge graph queries. The existing researches mainly focused on the query techniques based on subgraph isomorphism models, which are not readily applied to the massive knowledge graphs. This project studies query models, distributed query algorithms and query platforms for knowledge graph queries. Specifically, it designs effective and efficient query processing techniques for the noisy and massive knowledge graphs. We first propose a query model for knowledge graphs by finding the subgraphs that are most similar to a given query graph; we then design a distributed indexing technique for billion-node knowledge graphs to accelerate query processing; at last, we propose the optimization techniques that are based on a shared-memory technique and a novel graph-computation workflow model, which reduce the querying time in a distributed environment. These proposed techniques would be able to enable the next-generation search engines to support the knowledge graphs queries.

知识图谱是描述现实世界中地点、人物等事物以及事物间联系的关系网络，为下一代搜索引擎提供重要数据支撑。知识图谱具有数据量庞大、信息不完整且噪声数据多的本质特征，故设计高效的知识图谱查询机制是当前的热点问题。然而，现有的查询技术大多基于单机环境和子图精确匹配模型，存在查询结果不完整、算法可扩展性差和查询时间长等问题。本项目从知识图谱查询模型、分布式查询算法、分布式查询执行优化三个层面对知识图谱查询问题展开研究，旨在提供快速高效的新型分布式查询技术。首先，研究基于子图近似匹配的知识图谱查询模型，以屏蔽不完整信息和噪声数据。其次，研究基于轻量级索引的分布式查询算法，达到快速响应查询请求的目的。最后，研究面向复杂查询的分布式图计算执行优化机制，进一步优化分布式知识图谱查询的运行时间。本项目成果将为下一代搜索引擎提供行之有效的解决方案，更可推广到于商业分析、生物信息等诸多领域，具有较高的应用价值。

本项目针对亿级顶点知识图谱的分布式查询优化问题展开研究。首先，研究了亿级节点知识图谱的查询问题，提出子图近似匹配模型，能够在超过10亿顶点的知识图谱上进行大于5个节点的近似查询；其次，在查询模型通用求解框架基础上，从轻量级索引的角度对查询任务进行加速，研究分析了轻量级图索引构建方法和基于索引的查询算法，使知识图谱的查询响应时间控制在10秒内；最后，研究面向复杂查询的分布式图计算执行优化技术，综合考虑数据分布、数据加载速度、系统部署效率和复杂查询执行效率等因素，对分布式查询系统的查询任务进行优化，提出分布式图计算工作流模型，设计了面复杂查询的分布式图计算执行优化策略，分布式系统加速比大于1.5，查询初始化时间小于5秒。基于上述理论研究成果，项目组开发实现了面向知识图谱查询的分布式图计算系统。本研究成果能为大规模知识图谱分布式查询提供一定的理论支持和技术借鉴，同时对 于分布式图计算、分布式大数据处理领域的研究提供有益借鉴，同时对于智慧城市、智慧医疗等领域的语义查询具有积极的参考意义。