Research On Large-scale Dynamic Graph Processing System Optimization

Large-scale dynamic graph data is widely used in real life and it is constantly changing.The dynamic nature of graphs increases the complexity of graph processing problems.The solution on traditional static graphs cannot directly applied to the processing of dynamic graphs.Thus,dynamic graph processing system and related technologies have become an important research direction.While the existing dynamic graph solution on stand-alone machine mainly adopts linked list to storage graph.A linked list is expensive to access arbitrary locations,and it is unfavorable for coalesced memory accesses,which affects the performance of update ingestion.An efficient dynamic graph processing system,named as IndexGraph,proposes an indexing mechanism.The mechanism organizes the adjacency lists of vertices in a dynamic graph with indexing structures to improve the efficiency of dynamic graph processing system on a single server.Compared with the linked list approach used by the state-of-art system(Stinger),the indexing mechanism achieves more coalesced memory accesses during the adjacency list scanning.Moreover,with indexing,sophisticated data structures can be used to organize the adjacency lists to further reduce the time paid on list updating.IndexGraph examines the bi-parental heap(beap)and proposes a hybrid update scheme.The hybrid scheme choose the batch update scheme and the beap-based update scheme adaptively.When the graph under processing graows large during evolution,the hybrid scheme improves the performance of the system.Compared to Stinger that uses linked list and batch update scheme,IndexGraph performs better.Experimental results show that IndexGraph consumes close amount of memory as the linked list approach when storing the same real-world graph.Moreover,IndexGraph achieves 1.47 x to 4x performance speedups on update ingestion and 1.1x to 10.6x performance speedups pn graph algorithm execution.