2014 BalancedGraphEdgePartition

• (Bourse et al., 2014) ⇒ Florian Bourse, Marc Lelarge, and Milan Vojnovic. (2014). “Balanced Graph Edge Partition.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623660

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Balanced+Graph+Edge+Partition
• http://dl.acm.org/citation.cfm?id=2623330.2623660&preflayout=flat#citedby

Quotes

Author Keywords

• Approximation algorithms; distributed massive computation; general; graph edge partition; graph theory; graphs and networks; streaming heuristics

Abstract

Balanced edge partition has emerged as a new approach to partition an input graph data for the purpose of scaling out parallel computations, which is of interest for several modern data analytics computation platforms, including platforms for iterative computations, machine learning problems, and graph databases. This new approach stands in a stark contrast to the traditional approach of balanced vertex partition, where for given number of partitions, the problem is to minimize the number of edges cut subject to balancing the vertex cardinality of partitions. In this paper, we first characterize the expected costs of vertex and edge partitions with and without aggregation of messages, for the commonly deployed policy of placing a vertex or an edge uniformly at random to one of the partitions. We then obtain the first approximation algorithms for the balanced edge-partition problem which for the case of no aggregation matches the best known approximation ratio for the balanced vertex-partition problem, and show that this remains to hold for the case with aggregation up to factor that is equal to the maximum in-degree of a vertex. We report results of an extensive empirical evaluation on a set of real-world graphs, which quantifies the benefits of edge - vs. vertex-partition, and demonstrates efficiency of natural greedy online assignments for the balanced edge-partition problem with and with no aggregation.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 BalancedGraphEdgePartition	Florian Bourse Marc Lelarge Milan Vojnovic			Balanced Graph Edge Partition				10.1145/2623330.2623660		2014