Research On Streaming Graph Partitioning Based On Multiple Loader

Extracting knowledge by performing computations on graphs is becomingincreasingly challenging as graphs grow in size, especially when performed in thelimited models of computation afforded to modern large scale computingsystems.The tractability of large-scale graph computations often hinges upon theability to efficiently partition a graph for distributed computation.But performingcomputations on a distributed graph is expensive if large amount of data have to bemoved. Without partitioning the graph, communication quickly becomes a limitingfactor in scaling the system up.Partitioning massive graphs for distributedcomputation can greatly decrease both network communication and runtime.Existing graph partitioning heuristics incur high computation andcommunication cost on large graphs. The graph has to be loaded into the distributedSystems, we need to look for the partitioning which can be done at the same timewith a lightweight streaming algorithm.The loader must make a decision about thelocation of each node as it is loaded. The goal is to find a close to optimal balancedpartitioning with as little computation as possible. This problem is also calledstreaming graph partitioning. Streaming graph partitioning is to partition the node setof a graph into k balanced disjoint subsets by serially examining only individualnodes and their local adjacency list.This paper presents an static streaming graph partitioning algorithm based onmultiple loader.The goal is to remove the bottleneck caused by the serial input.Thisalgorithm first divides the graph streaming into multiple streaming,then parallel loadinto multiple machines to calculate, through a pretreatment process to eliminate coldstart problem of the algorithm.At last, optimize the result can get less edge-cut.This paper also introduce an dynamic streaming graph partitioning algorithmbased on multiple loader. Because of the characteristic in dynamic graph, if we applythe algorithm on the dynamic graph，the computation will be very large. In thisalgorithm, we compute only the dynamic part. The computation will be largelyreduced. At last, optimize algorithm is also based on the dynamic. Finally，through experiment on large graph data set, we can conclude wherethey can apply by compare multiple loaders with simple loader. Through the changeof the number that used in these experiments, the result shows that the number ofloaders does little matter about the partition. At last, through simulation on dynamicgraph data, the result shows multiple streaming partition can apply for dynamic graphtoo.