Power-PCSR:An Efficient Dynamic Graph Storage Structure for Power-law Graphs
Graph data is widespread in real life and changes over time.The traditional efficient static graph storage structure,compressed sparse row/column(CSR/CSC)requires a large amount of data migration when inserting/deleting edges to/from graphs,which is not suitable for dynamic graphs.Although the adjacency list(AL)is able to update graphs efficiently,it is ineffi-cient in reading and analyzing graphs since it has a large number of pointers,which results in random memory access.PCSR is a novel dynamic graph storage structure based on CSR.It employs a packed memory arrays(PM A)to store the edges rather than a continuous array.Because there are empty slots in PM A,it is easier to insert/delete edges.Thus,packed compressed sparse row(PCSR)is efficient in both graph updating and analysis.However,we find that the performance of PCSR suffers from large de-gree vertices when storing power-law graphs.For this,this paper proposes a new graph storage structure based on PCSR,Power-PCSR,which supports efficient updating and analysis of dynamic power-law graphs.In Power-PCSR,each large-degree vertex is stored in an independent PM A separately,and other vertices with small degrees are stored in a PM A.The data migration caused by the small-degree vertices will not lead to the migration of large-degree vertices,thus greatly reducing the amount of data mi-gration.Similarly,the data migration caused by the update of large-degree vertices is only limited to its PM A,and will not involve the data migration of other large-degree vertices and small-degree vertices.Experiments show that Power-PCSR has similar per-formance to PCSR when analyzing graphs,and is 2 times faster than PCSR when updating graph data.
万方数据
维普
