On Storage And Processing Methods Of Historical Graph Data

As a graph data structure depicting the continuous change of the graph network with the time dimension,the historical graph is showing its application and research value in more and more scenarios.This paper starts with historical graph data and starts to study the storage and processing methods of it.Based on the Rocks DB storage engine,this paper designs and implements the historical graph database Hist DB to efficiently store and retrieve historical graph data.Hist DB stores historical graph changing data based on the K-V storage model,and combines four types of historical graph vertex retrieval,graph changing data retrieval,historical neighbor retrieval,and snapshot retrieval to design and implement an efficient data retrieval interface.In addition,Hist DB designed a data index block to optimize retrieval based on block-based storage.Experiments show that Hist DB's index optimization mechanism can effectively improve the performance of some data retrieval interfaces.In this paper,combined with the query requirements on historical graphs,the historical graph query language Hist QL is designed based on the Gremlin static graph query language by introducing the time dimension.Based on the Hist QL language,this paper also designs and implements the historical graph query processing framework Hist Query to calculate query statements.Hist Query uses a nested processing unit management method to achieve multi-level and multi-granular resource management and calculation scheduling.Besides,this paper also implements the multi-threaded computing framework of Hist Query based on the designed lockfree communication mechanism.This article also shows the multi-threaded query performance of Hist Query based on experimental testing,and analyzes the impact of graph division,configuration parameters,early termination mechanism and other factors on query calculation,with which the optimization mechanism of Hist Query are analyzed in this paper.Combining with the incompleteness of the definition of the existing historical graph model,this article also innovatively reflects the concept of time-weighted edges,and expands the historical graph model.Based on which,this paper also studies the path search technology on historical graphs,defines the path problem of the historical graph including the time weight edge,and uses the utility value function to measure the evaluation rules in the path search process.In this paper,a basic algorithm based on breadth-first search and an optimization algorithm based on one-pass scanning are designed to solve the path search problem of historical graphs.Experimental results show that the proposed one-pass scanning algorithm has higher search efficiency,and in the face of different input data distribution,the one-pass scanning algorithm also has better stability.