Design And Implementation Of A Graph Partitioning Algorithm For Distributed Graph Database

Due to the huge scale of graph data in distributed graph databases,it is necessary to divide the graph data into multiple subgraphs and store them on different work servers.The efficiency of query and computing tasks in distributed graph databases depends on the quality of graph partitioning which is determined by the graph partitioning algorithm.The state-of-the-art graph partitioning methods are divided into three categories:stream-based graph partitioning methods,distributed graph partitioning methods,and dynamic graph partitioning methods.They are often used in combination in distributed graph databases.Stream-based graph partitioning methods which use heuristics to load an initial huge graph is concerned.After analyzing popular stream-based graph partitioning methods,it is found that number of neighbors of nodes in different partitions is usually included in the basis of partitioning.But when considering the number of neighbors,only one-step neighbors are considered.In view of this deficiency,the strategy of considering multi-step neighbors is explored and attempted and finally a stream-based higher walk length heuristic vertexcut graph partitioning algorithm which is called LDGVC is purposed.The edges in the stream are heuristically partitioned using cluster information,the number of replicas of the node,and the load of the cluster as evaluation functions.The calculation of evaluation functions is also optimized.The evaluations suggest that the optimization strategy is effective,and the optimal walk length of the LDGVC algorithm is 2,and it has the ability to efficiently partition large graphs and reduce communication costs significantly compared to state-of-the-art graph partitioning algorithms.Relative to HDRF,it reduces the timing by 6% to 24%.