Stream-Based Vertex cut partitioning with Buffer support for Power-law graphs(SVBP)

Abstract

Evolution of online technologies and usage resulted in massive data collection, analyzing and visualizing such huge data through graphs has become one of the interesting areas of research.  The Big graphs created for massive data are very huge and cannot be processed by a simple machine at an adequate amount of time any-more. So the Big graphs are to be partitioned and stored on different machines to process and analyze them quickly.  Traditional graph partitioning methods can no longer does this task since it follows of-fline processing and requires to store and access the entire graph from one machine leading to memory bottlenecks and also  time consuming.  Hence, Streaming Graph partitioning methods have gained momentum and these methods can partition real time online graphs directly and efficiently.  Streaming graph partitioning me-thods takes stream of edges along with its end vertices as input into a Scheduler machine.  The scheduler machine intern partitions the graph and assigns the nodes and edges to different partitions as re-ceived. Since entire graph cannot be made available to the scheduler machine at any given point of time, it assigns edges to partition ma-chines based on using some partition criteria that may not be optimal. Scheduler’s decision can be notably improved if partitioning is done only after receiving sufficient information of the node or edge being allocated. This paper recommends an efficient Buffer-based edge streaming algorithm called SVBP for graph partitioning. This method implements the idea of delaying the assignment of few edges and restream them at right time to improve partitioning effi-ciency. Our method uses a Buffer to store the edges whose partition-ing is delayed. The SVBP algorithm is evaluated on real-time power-law graphs that are notably large.  Our method is able do the job of partitioning efficiently on all the graphs by keeping the replication factor minimum and balancing the load across partitions legitimately good compared to other algorithms.