PuLP: Scalable multi-objective multi-constraint partitioning for small-world networks

George M. Slota; Kamesh Madduri; Sivasankaran Rajamanickam

doi:10.1109/BigData.2014.7004265

PuLP: Scalable multi-objective multi-constraint partitioning for small-world networks

George M. Slota
, Kamesh Madduri
, Sivasankaran Rajamanickam

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

58 Scopus citations

Abstract

We present PuLP, a parallel and memory-efficient graph partitioning method specifically designed to partition low-diameter networks with skewed degree distributions. Graph partitioning is an important Big Data problem because it impacts the execution time and energy efficiency of graph analytics on distributed-memory platforms. Partitioning determines the in-memory layout of a graph, which affects locality, intertask load balance, communication time, and overall memory utilization of graph analytics. A novel feature of our method PuLP (Partitioning using Label Propagation) is that it optimizes for multiple objective metrics simultaneously, while satisfying multiple partitioning constraints. Using our method, we are able to partition a web crawl with billions of edges on a single compute server in under a minute. For a collection of test graphs, we show that PuLP uses 8-39× less memory than state-of-the-art partitioners and is up to 14.5× faster, on average, than alternate approaches (with 16-way parallelism). We also achieve better partitioning quality results for the multi-objective scenario.

Original language	English (US)
Title of host publication	Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014
Editors	Jimmy Lin, Jian Pei, Xiaohua Tony Hu, Wo Chang, Raghunath Nambiar, Charu Aggarwal, Nick Cercone, Vasant Honavar, Jun Huan, Bamshad Mobasher, Saumyadipta Pyne
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	481-490
Number of pages	10
ISBN (Electronic)	9781479956654
DOIs	https://doi.org/10.1109/BigData.2014.7004265
State	Published - 2014
Event	2nd IEEE International Conference on Big Data, Big Data 2014 - Washington, United States Duration: Oct 27 2014 → Oct 30 2014

Publication series

Name	Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014

Conference

Conference	2nd IEEE International Conference on Big Data, Big Data 2014
Country/Territory	United States
City	Washington
Period	10/27/14 → 10/30/14

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

All Science Journal Classification (ASJC) codes

Artificial Intelligence
Information Systems

Access to Document

10.1109/BigData.2014.7004265

Cite this

Slota, G. M., Madduri, K., & Rajamanickam, S. (2014). PuLP: Scalable multi-objective multi-constraint partitioning for small-world networks. In J. Lin, J. Pei, X. T. Hu, W. Chang, R. Nambiar, C. Aggarwal, N. Cercone, V. Honavar, J. Huan, B. Mobasher, & S. Pyne (Eds.), Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014 (pp. 481-490). Article 7004265 (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigData.2014.7004265

Slota, George M. ; Madduri, Kamesh ; Rajamanickam, Sivasankaran. / PuLP : Scalable multi-objective multi-constraint partitioning for small-world networks. Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014. editor / Jimmy Lin ; Jian Pei ; Xiaohua Tony Hu ; Wo Chang ; Raghunath Nambiar ; Charu Aggarwal ; Nick Cercone ; Vasant Honavar ; Jun Huan ; Bamshad Mobasher ; Saumyadipta Pyne. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 481-490 (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014).

@inproceedings{f53c95789c234a11a47317e320e779cd,

title = "PuLP: Scalable multi-objective multi-constraint partitioning for small-world networks",

abstract = "We present PuLP, a parallel and memory-efficient graph partitioning method specifically designed to partition low-diameter networks with skewed degree distributions. Graph partitioning is an important Big Data problem because it impacts the execution time and energy efficiency of graph analytics on distributed-memory platforms. Partitioning determines the in-memory layout of a graph, which affects locality, intertask load balance, communication time, and overall memory utilization of graph analytics. A novel feature of our method PuLP (Partitioning using Label Propagation) is that it optimizes for multiple objective metrics simultaneously, while satisfying multiple partitioning constraints. Using our method, we are able to partition a web crawl with billions of edges on a single compute server in under a minute. For a collection of test graphs, we show that PuLP uses 8-39× less memory than state-of-the-art partitioners and is up to 14.5× faster, on average, than alternate approaches (with 16-way parallelism). We also achieve better partitioning quality results for the multi-objective scenario.",

author = "Slota, \{George M.\} and Kamesh Madduri and Sivasankaran Rajamanickam",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2nd IEEE International Conference on Big Data, Big Data 2014 ; Conference date: 27-10-2014 Through 30-10-2014",

year = "2014",

doi = "10.1109/BigData.2014.7004265",

language = "English (US)",

series = "Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "481--490",

editor = "Jimmy Lin and Jian Pei and Hu, \{Xiaohua Tony\} and Wo Chang and Raghunath Nambiar and Charu Aggarwal and Nick Cercone and Vasant Honavar and Jun Huan and Bamshad Mobasher and Saumyadipta Pyne",

booktitle = "Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014",

address = "United States",

}

Slota, GM, Madduri, K & Rajamanickam, S 2014, PuLP: Scalable multi-objective multi-constraint partitioning for small-world networks. in J Lin, J Pei, XT Hu, W Chang, R Nambiar, C Aggarwal, N Cercone, V Honavar, J Huan, B Mobasher & S Pyne (eds), Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014., 7004265, Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014, Institute of Electrical and Electronics Engineers Inc., pp. 481-490, 2nd IEEE International Conference on Big Data, Big Data 2014, Washington, United States, 10/27/14. https://doi.org/10.1109/BigData.2014.7004265

PuLP: Scalable multi-objective multi-constraint partitioning for small-world networks. / Slota, George M.; Madduri, Kamesh; Rajamanickam, Sivasankaran.
Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014. ed. / Jimmy Lin; Jian Pei; Xiaohua Tony Hu; Wo Chang; Raghunath Nambiar; Charu Aggarwal; Nick Cercone; Vasant Honavar; Jun Huan; Bamshad Mobasher; Saumyadipta Pyne. Institute of Electrical and Electronics Engineers Inc., 2014. p. 481-490 7004265 (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - PuLP

T2 - 2nd IEEE International Conference on Big Data, Big Data 2014

AU - Slota, George M.

AU - Madduri, Kamesh

AU - Rajamanickam, Sivasankaran

PY - 2014

Y1 - 2014

N2 - We present PuLP, a parallel and memory-efficient graph partitioning method specifically designed to partition low-diameter networks with skewed degree distributions. Graph partitioning is an important Big Data problem because it impacts the execution time and energy efficiency of graph analytics on distributed-memory platforms. Partitioning determines the in-memory layout of a graph, which affects locality, intertask load balance, communication time, and overall memory utilization of graph analytics. A novel feature of our method PuLP (Partitioning using Label Propagation) is that it optimizes for multiple objective metrics simultaneously, while satisfying multiple partitioning constraints. Using our method, we are able to partition a web crawl with billions of edges on a single compute server in under a minute. For a collection of test graphs, we show that PuLP uses 8-39× less memory than state-of-the-art partitioners and is up to 14.5× faster, on average, than alternate approaches (with 16-way parallelism). We also achieve better partitioning quality results for the multi-objective scenario.

AB - We present PuLP, a parallel and memory-efficient graph partitioning method specifically designed to partition low-diameter networks with skewed degree distributions. Graph partitioning is an important Big Data problem because it impacts the execution time and energy efficiency of graph analytics on distributed-memory platforms. Partitioning determines the in-memory layout of a graph, which affects locality, intertask load balance, communication time, and overall memory utilization of graph analytics. A novel feature of our method PuLP (Partitioning using Label Propagation) is that it optimizes for multiple objective metrics simultaneously, while satisfying multiple partitioning constraints. Using our method, we are able to partition a web crawl with billions of edges on a single compute server in under a minute. For a collection of test graphs, we show that PuLP uses 8-39× less memory than state-of-the-art partitioners and is up to 14.5× faster, on average, than alternate approaches (with 16-way parallelism). We also achieve better partitioning quality results for the multi-objective scenario.

UR - https://www.scopus.com/pages/publications/84921727521

UR - https://www.scopus.com/pages/publications/84921727521#tab=citedBy

U2 - 10.1109/BigData.2014.7004265

DO - 10.1109/BigData.2014.7004265

M3 - Conference contribution

AN - SCOPUS:84921727521

T3 - Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014

SP - 481

EP - 490

BT - Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014

A2 - Lin, Jimmy

A2 - Pei, Jian

A2 - Hu, Xiaohua Tony

A2 - Chang, Wo

A2 - Nambiar, Raghunath

A2 - Aggarwal, Charu

A2 - Cercone, Nick

A2 - Honavar, Vasant

A2 - Huan, Jun

A2 - Mobasher, Bamshad

A2 - Pyne, Saumyadipta

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 27 October 2014 through 30 October 2014

ER -

Slota GM, Madduri K, Rajamanickam S. PuLP: Scalable multi-objective multi-constraint partitioning for small-world networks. In Lin J, Pei J, Hu XT, Chang W, Nambiar R, Aggarwal C, Cercone N, Honavar V, Huan J, Mobasher B, Pyne S, editors, Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 481-490. 7004265. (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014). doi: 10.1109/BigData.2014.7004265

PuLP: Scalable multi-objective multi-constraint partitioning for small-world networks

Abstract

Publication series

Conference

UN SDGs

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this