Jiewen Huang
Daniel J. Abadi
Abstract
This paper introduces a dynamic graph partitioning algorithm, designed for large, constantly changing graphs. We propose a partitioning framework that adjusts on the fly as the graph structure changes. We also introduce a replication algorithm that is tightly integrated with the partitioning algorithm, which further reduces the number of edges cut by the partitioning algorithm. Even though the proposed approach is handicapped by only taking into consideration local parts of the graph when reassigning vertices, extensive evaluation shows that the proposed approach maintains a quality partitioning over time, which is comparable at any point in time to performing a full partitioning from scratch using a state-the-art static graph partitioning algorithm such as METIS. Furthermore, when vertex replication is turned on, edge-cut can improve by an order of magnitude.
- K. Andreev and H. Räcke. Balanced graph partitioning. In ACM Symposium on Parallelism in Algorithms and Architectures '04.Google Scholar
- A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.Google Scholar
- S. T. Barnard. Pmrsb: Parallel multilevel recursive spectral bisection. In Supercomputing '95.Google Scholar
- V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008.Google Scholar
- C. Chevalier and F. Pellegrini. Pt-scotch: A tool for efficient parallel graph ordering. Parallel Comput. '08.Google Scholar
- C. Curino, E. Jones, Y. Zhang, and S. Madden. Schism: A workload-driven approach to database replication and partitioning. PVLDB, 3(1), 2010.Google Scholar
- Q. Duong, S. Goel, J. Hofman, and S. Vassilvitskii. Sharding social networks. In Proc. of WSDM, 2013.Google ScholarDigital Library
- G. Even, J. S. Naor, S. Rao, and B. Schieber. Fast approximate graph partitioning algorithms. In SODA '97.Google Scholar
- C. Fiduccia and R. Mattheyses. A linear-time heuristic for improving network partitions. In DAC 1982.Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computers and intractability. 1979.Google ScholarDigital Library
- M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified np-complete problems. In STOC '74.Google Scholar
- B. Hendrickson and R. Leland. A multilevel algorithm for partitioning graphs. In Supercomputing, 1995.Google ScholarDigital Library
- J. Huang, D. J. Abadi, and K. Ren. Scalable sparql querying of large rdf graphs. In PVLDB '11.Google Scholar
- U. Kang, H. Tong, J. Sun, C.-Y. Lin, and C. Faloutsos. Gbase: a scalable and general graph management system. In KDD'11.Google Scholar
- U. Kang, C. E. Tsourakakis, and C. Faloutsos. Pegasus: A peta-scale graph mining system. In ICDM'09.Google Scholar
- D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and D. Lewin. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In Proc. of STOC, 1997.Google ScholarDigital Library
- G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 1998.Google Scholar
- G. Karypis and V. Kumar. A parallel algorithm for multilevel graph partitioning and sparse matrix ordering. J. Parallel Distrib. Comput., 1998.Google Scholar
- B. W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. The Bell system technical journal, 1970.Google Scholar
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: Densification laws, shrinking diameters and possible explanations. In KDD '05.Google Scholar
- Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. Graphlab: A new parallel framework for machine learning. In UAI, 2010.Google ScholarDigital Library
- G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD'10.Google Scholar
- J. Mondal and A. Deshpande. Managing large dynamic graphs efficiently. In SIGMOD '12.Google Scholar
- M. E. Newman. Modularity and community structure in networks. PNAS, 2006.Google ScholarCross Ref
- J. Nishimura and J. Ugander. Restreaming graph partitioning: Simple versatile algorithms for advanced balancing. In KDD '13.Google Scholar
- F. Pellegrini and J. Roman. Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. In HPCN Europe '96.Google Scholar
- J. M. Pujol, V. Erramilli, G. Siganos, X. Yang, N. Laoutaris, P. Chhabra, and P. Rodriguez. The little engine(s) that could: scaling online social networks. In SIGCOMM '10.Google Scholar
- A. Quamar, K. A. Kumar, and A. Deshpande. Sword: Scalable workload-aware data placement for transactional workloads. In Proc. of EDBT, 2013.Google ScholarDigital Library
- U. N. Raghavan, R. Albert, and S. Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007.Google Scholar
- M. Sarwat, S. Elnikety, Y. He, and G. Kliot. Horton: Online query execution engine for large distributed graphs. In ICDE '12.Google Scholar
- K. Schloegel, G. Karypis, and V. Kumar. Multilevel diffusion schemes for repartitioning of adaptive meshes. J. Parallel Distrib. Comput., 1997.Google Scholar
- K. Schloegel, G. Karypis, and V. Kumar. Parallel static and dynamic multi-constraint graph partitioning. Concurrency and Computation: Practice and Experience, 2002.Google ScholarCross Ref
- K. Schloegel, G. Karypis, and V. Kumar. Sourcebook of parallel computing. chapter Graph Partitioning for High-performance Scientific Simulations. 2003.Google Scholar
- B. Shao, H. Wang, and Y. Li. Trinity: A distributed graph engine on a memory cloud. In SIGMOD '13.Google Scholar
- I. Stanton and G. Kliot. Streaming graph partitioning for large distributed graphs. In KDD '12.Google Scholar
- M. Stonebraker, D. J. Abadi, A. Batkin, X. Chen, M. Cherniack, M. Ferreira, E. Lau, A. Lin, S. Madden, E. O'Neil, P. O'Neil, A. Rasin, N. Tran, and S. Zdonik. C-store: A column-oriented dbms. In Proc. of VLDB, 2005.Google Scholar
- C. Tsourakakis, C. Gkantsidis, B. Radunovic, and M. Vojnovic. Fennel: Streaming graph partitioning for massive scale graphs. In WSDM '14.Google Scholar
- J. Ugander and L. Backstrom. Balanced label propagation for partitioning massive graphs. In Proc. of WSDM, 2013.Google ScholarDigital Library
- L. Vaquero, F. Cuadrado, D. Logothetis, and C. Martella. Adaptive partitioning for large-scale dynamic graphs. In ICDCS '14.Google Scholar
- C. Walshaw, M. G. Everett, and M. Cross. Parallel dynamic graph partitioning for adaptive unstructured meshes. J. Parallel Distrib. Comput., 1997.Google Scholar
- L. Wang, Y. Xiao, B. Shao, and H. Wang. How to partition a billion-node graph. In ICDE '14.Google Scholar
- N. Xu, L. Chen, and B. Cui. Loggp: A log-based dynamic graph partitioning method. PVLDB, 2014.Google ScholarDigital Library
Index Terms
- Leopard: lightweight edge-oriented partitioning and replication for dynamic graphs
Recommendations
On the Multichromatic Number of s-Stable Kneser Graphs
For positive integers n and s, a subset Sï [n] is s-stable if sï |i-j|ï n-s for distinct i,j∈S . The s-stable r-uniform Kneser hypergraph KGrn,ks-stable is the r-uniform hypergraph that has the collection of all s-stable k-element subsets of [n] as ...
Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes
An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the ...
Forbidden Subgraphs and Weak Locally Connected Graphs
A graph is called H-free if it has no induced subgraph isomorphic to H. A graph is called $$N^i$$Ni-locally connected if $$G[\{ x\in V(G): 1\le d_G(w, x)\le i\}]$$G[{x?V(G):1≤dG(w,x)≤i}] is connected and $$N_2$$N2-locally connected if $$G[\{uv: \{uw, vw\...
Comments