Maiter: An Asynchronous Graph Processing Framework for Delta-Based Accumulative Iterative Computation
- 16 September 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 25 (8), 2091-2100
- https://doi.org/10.1109/tpds.2013.235
Abstract
Myriad of graph-based algorithms in machine learning and data mining require parsing relational data iteratively. These algorithms are implemented in a large-scale distributed environment to scale to massive data sets. To accelerate these large-scale graph-based iterative computations, we propose delta-based accumulative iterative computation (DAIC). Different from traditional iterative computations, which iteratively update the result based on the result from the previous iteration, DAIC updates the result by accumulating the “changes” between iterations. By DAIC, we can process only the “changes” to avoid the negligible updates. Furthermore, we can perform DAIC asynchronously to bypass the high-cost synchronous barriers in heterogeneous distributed environments. Based on the DAIC model, we design and implement an asynchronous graph processing framework, Maiter. We evaluate Maiter on local cluster as well as on Amazon EC2 Cloud. The results show that Maiter achieves as much as 60 × speedup over Hadoop and outperforms other state-of-the-art frameworks.Keywords
This publication has 19 references indexed in Scilit:
- PrIterPublished by Association for Computing Machinery (ACM) ,2011
- HaLoopProceedings of the VLDB Endowment, 2010
- Asynchronous Algorithms in MapReducePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- TwisterPublished by Association for Computing Machinery (ACM) ,2010
- Parallel Pairwise ClusteringPublished by Society for Industrial & Applied Mathematics (SIAM) ,2009
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Distributed snapshotsACM Transactions on Computer Systems, 1985
- Distributed asynchronous computation of fixed pointsMathematical Programming, 1983
- Asynchronous Iterative Methods for MultiprocessorsJournal of the ACM, 1978
- Chaotic relaxationLinear Algebra and its Applications, 1969