Dynamic power law diagram storage method based on LSM tree

Abstract

The invention discloses a dynamic power law diagram storage method based on an LSM tree, and the method comprises the steps: carrying out the statistics of the out-degree information of the vertexes of a diagram during the dynamic updating of diagram data, and carrying out the separated storage of the large-degree vertexes and common vertexes in the form of a memory vertex table; allocating memories for the large vertex table and the common vertex table according to a power law distribution proportion; and when the data volume of each vertex table exceeds a threshold value, performing concurrent overwriting on the graph data according to the thread count corresponding to the memory allocation proportion. According to the method, the problems of data merging overhead, storage resource waste and the like caused by frequent updating of graph data based on power law distribution can be relieved, and the method has good practical value and prospect in the field of knowledge graphs and graph calculation.

Description

technical field [0001] The invention belongs to the technical field of computers, and in particular relates to a data storage method of a dynamic power-law graph based on an LSM tree. Background technique [0002] In recent years, graph computing has been increasingly used in fields such as complex networks, deep learning, brain science, and community discovery. With the increasing scale and complexity of graph datasets, how to design an efficient graph storage mechanism has attracted more and more attention. In response to this problem, there have been PB-level distributed file systems based on key-value pairs such as GFS (Google File System) and HDFS (Hadoop File System). The sequential reading of the hard disk is more efficient than random reading, so as to improve the throughput and have good scalability. [0003] However, in a real network, graph data is often updated in real time, and there is a scale-free phenomenon in the degree distribution, that is, the node degr...

AI Technical Summary

Problems solved by technology

[0004] Purpose of the invention: In order to solve the problems existing in the existing graph storage technology, the present invention provides a dynamic power-law graph storage method based on the LSM tree, which stores the low-degree vertices and the high-degree vertices separately, and according to the power of the current degree of the graph data Allocate memory with statistical information based on power-law distribution, and configure the corresponding number of concurrent overflow writing threads, which can alleviate the problems of data merging overhead and storage resource waste caused by frequent graph data updates based on power-law distribution, and is suitable for storing data with dynamic graph structures

Images