基于外存的海量知识图谱数据的查询处理

Knowledge graph is a widely-used model, which tracks both the entity and the relationship between different entities and It has been broadly applied into many fields. For the big knowledge graph, a common but important operation is to query the graph to find related information. However, with the scale of the knowledge graph being expanded at high speed, it is difficult to process the queries efficiently for the knowledge graphs as they are too large to fit into the main memory of a machine. In this situation, it will cost high during the query processing. Existing approaches always focus on two aspects. The first is to find the meaningful results for a query. In this situation, the semantics of the knowledge graph will be considered more and the existing solutions consider little about the efficiency of the query processing when the data size exceeds the limit of the memory size. The other aspect is to focus on the efficient processing of the big graph data while consider little about the labels in the knowledge graph. In this proposal, we aim to consider both of these aspects at the same time. That is, we not only propose the methods to the external-memory based graph processing, but also consider the effects of the semantics in the knowledge graph. Unlike the exiting in-memory knowledge graph query processing and external-memory graph algorithms, we propose a contract & expand framework for the knowledge graph query processing. First, we contract the knowledge graph according to the semantics and make sure that the queries can be evaluated on the contracted graph. After receiving the results on the contracted knowledge graph, we expand according to the graph structure. Under this framework, the graph size needs to be considered will be reduced in a large scale. However, there are still many challenges under this framework, such as how to minimize the size of the contracted graph, how to design different contracted algorithms according to different kinds of queries etc. Thus, it is important to do research on the external-memory based knowledge graph query processing. We believe that the result of the research in this project can contribute to improving not only the efficiency of the query processing, but also the scalability for the knowledge graph queries.

知识图谱是一种记录实体以及实体间关系的模型并被广泛应用于各个领域。针对知识图谱，一类重要的操作就是查询图谱中实体的相关信息。但是随着数据规模的扩大，其规模已经超过大多数计算机内存的容量。在此情况下，对其进行查询将产生极大的开销。已有的对知识图谱的研究侧重于对查询结果的语义研究, 而很少考虑其规模对效率的影响。另一方面，一般图数据的外存算法只考虑结构本身，而不考虑语义。本项目将二者有效的结合，在对大规模知识图谱的查询处中，同时利用语义以及结构对图谱进行切割与压缩，使得查询可以在压缩图上进行。进而根据压缩图的结果拓展得到原图的查询结果。该框架可以有效的减少查询处理所涉及的图的规模。但是，该框架仍有诸多挑战，包括如何最大的压缩图谱的规模以及设计不同的压缩策略等。因此，对基于外存的海量知识图谱的查询处理的研究十分必要。相信本项目的研究成果可以很好的提高对知识图谱查询处理的效率以及可处理的数据规模。

本项目执行时间为2017.1-2019.12，这期间主要研究了知识图谱的高效查询处理算法，现总结如下：.知识图谱是一种记录实体以及实体间关系的模型并被广泛应用于各个领域。由于节点以及边的属性信息，其在结构和语义方面比一般的线性链或树的结构更具有一般性的表示能力。但同时，也带来了查询处理更为复杂的问题。同时，知识图谱的规模随着信息爆炸式的增长，其规模已经超过大多数计算机内存的容量。如何针对大规模的知识图谱，进行查询的高效处理成为一个新的挑战。在本项目中，我们完成以下工作：.1.在知识图谱的存储与子图查询方面，项目组提出了基于顺序访问的子图匹配查询算法，将开销较大的随机访问转化为开销较小的顺序访问。同时，利用数据本身的属性信息，提出了查询自动填充算法、基于查询结果的推荐算法等。.2.在模式查询处理算法方面，项目组提出了统一的并行处理框架，它可以高效地处理针对图数据的模式匹配、频繁模式挖掘、稠密图计算、核心图计算分析任务。同时，该框架采用轻量级的并行处理策略，可无缝的集成到多个已有的图分析系统中。.3.在实体匹配算法中，项目组提出了基于公有图以及隐私图的模型，它可以同时考虑公开的图数据信息以及用户特有的图数据结构，从而可以高效地挖掘相关的匹配的实体信息。同时，项目组研究了基于地理信息的实体匹配算法与应用，进一步提高了查询的准确率。.4.本项目实施过程中，项目组已在ICDE，KDD，AAAI等国际顶级会议上发表多篇论文且开发的原型系统已经得到应用。