Paper Info
Title
PaPar: A Parallel Data Partitioning Framework for Big Data Applications
Abstract
Today, big data applications can generate large-scale data sets at an unprecedented rate; and scientists have turned to parallel and distributed systems for data analysis. Although many big data processing systems provide advanced mechanisms to partition data and tackle the computational skew, it is difficult to efficiently implement skew-resistant mechanisms, because the runtime of different partitions not only depends on input data size but also algorithms that will be applied on data. As a result, many research efforts have been undertaken to explore user-defined partitioning methods for different types of applications and algorithms. However, manually writing application-specific partitioning methods requires significant coding effort, and finding the optimal data partitioning strategy is particularly challenging even for developers that have mastered sufficient application knowledge. In this paper, we propose PaPar, a Parallel data Partitioning framework for big data applications, to simplify the implementations of data partitioning algorithms. PaPar provides a set of computational operators and distribution strategies for programmers to describe desired data partitioning methods. Taking an input data configuration file and a workflow configuration file as the input, PaPar can automatically generate the parallel partitioning codes by formalizing the user-defined workflow as a sequence of key-value operations and matrix-vector multiplications, and efficiently mapping to the parallel implementations with MPI and MapReduce. We apply our approach on two applications: muBLAST, a MPI implementation of BLAST algorithms for biological sequence search; and PowerLyra, a computation and partitioning method for skewed graphs. The experimental results show that compared to the partitioning methods of applications, the codes generated by PaPar can produce the same data partitions with comparable or less partitioning time.
Year
DOI
Venue
2017
10.1109/IPDPS.2017.119
2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
Keywords
Field
DocType
Partition,Skew,Big Data,MapReduce,MPI
Data structure,Data set,Algorithm design,Computer science,Parallel computing,Coding (social sciences),Skew,Distributed database,Workflow,Big data,Distributed computing
Conference
ISSN
ISBN
Citations 
1530-2075
978-1-5386-3915-3
2
PageRank 
References 
Authors
0.36
35
5
Name
Order
Citations
PageRank
Hao Wang140224.64
Jing Zhang2706.53
Da Zhang3122.25
Sarunya Pumma4212.69
Wu-chun Feng52812232.50