Research Of Path Query Processing Algorithms And System On Time-dependent Graph

The time-dependent graph is a graph data model which introduces the time dimension to the traditional static graph,and its data changes with time.The time-dependent graph model can describe the problems in a more realistic way,so more and more research work is carried out in related aspects.This article starts with the time-dependent graph model,aiming at the design of the time-dependent graph system framework and the research of algorithms on the time-dependent graph.Based on the Neo4j graph database,this paper designs and implements a system framework named TD-Frame that can store time-dependent graphs persistently.The framework uses the Neo4j graph database as the storage medium for time-dependent graphs,and uses user-defined functions provided by Neo4j to implement common timedependent related functions.It can provide users with the application program interface for writing time-dependent graph-related applications on the framework.The experiment tested the running time of the application program interface,and at the same time,a sample program was used to test the performance of the framework.The results show that the TD-Frame framework can provide better support for the development of time-dependent graph-related applications.Different from the Page Rank algorithm on the traditional static graph,this paper proposes the Page Rank algorithm on the discrete time-dependent graph model.After the introduction of the time dimension,the meaning of the Page Rank question can be more rich and full.Based on the TD-Frame framework and modifying the classic Page Rank algorithm,we can get the Page Rank algorithm on the discrete time-dependent graph(His Page Rank).At the same time,through experiments,we explored the impact of graph data size and convergence threshold on the running time of His Page Rank algorithm and the percentage of points and edges retrieved on average by snapshots.Combining the existing work on the path search problem on continuous timedependent graphs,this paper proposes the concept of "generalized optimal",and based on this concept,proposes the generalized optimal path problem.Through the exploration of the characteristics of the continuous time-dependent graph model,this paper proposes an algorithm for solving the generalized optimal path problem and analyzes the algorithm.Experiments have explored the impact of data size and other parameters on the running time of the algorithm,and compared the algorithm proposed in this paper with the other two algorithms.The experiment result shows that the algorithm can solve the problem with good efficiency.