Research On Regular Path Queries Over Distributed Knowledge Graphs Based On General Partial Evaluation

Recently,the knowledge graph has been playing an important role in the field of Artificial Intelligence,which is powerful enough in processing semantic and connecting entities of the real-world.Regular path query,as one of the most popular navigational queries,has become a research focus and been widely studied and discussed.Along with the development of the Internet,the scale of the knowledge graph expands rapidly as well.Therefore,it's inevitable to employ distributed systems to handle large-scale datasets.Some partial evaluation approach has been applied on graph query based on the distributed system,but some partial intermediate results are produced and lead to the bottleneck of computation and communication.Based on the theory of partial evaluation,we propose a general partial evaluation model named GPE,which consists of one master node and multiple slave nodes.Two phases are contained in the GPE model: distributed computation and centralized computation.It divides the distributed computing process into an alternating sequence of partial computation and communication between nodes.In this process,each node is parallel processed and the time of the communication among nodes can be controlled by parameter k.Based on this model,a distributed regular path query algorithm GPERPQ is designed in this paper.GPERPQ transfers a regular path query into k+1 partial computations and k message transmissions.Besides,the master node is connected with the client,which is responsible for receiving the query,querying resolution,task distribution and centralized computation.Based on the Actor model,slave nodes are responsible for receiving messages,partial path matching and messages sending.Compared with partial evaluation,the GPE model can not only handle the bottleneck caused by the master node's computation and communication in centralized computation,but it also can avoid generating partial intermediate results by using multiple partial computations with communication.Meanwhile,based on the analysis of cost,three optimal strategies are proposed: vertex mapping,the pre-judge for out-boundary nodes and middle results selection,and reducing the algorithm's communication cost and computation cost respectively.According to the regular path query by design,we validate the proposed algorithm on the benchmark and real-world dataset.The experimental results demonstrate that GPERPQ can be used on the distributed knowledge graphs and make regular path queries efficiently.The query time can be enhanced by a magnitude by adjusting parameter k,which realizes reducing computation cost by adding little communication cost among nodes.Finally,an effective method for regular path query over distributed knowledge graph is formed.