{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T23:25:25Z","timestamp":1791329125828,"version":"4.3.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>Parallel dataflow systems are a central part of most analytic pipelines for big data. The iterative nature of many analysis and machine learning algorithms, however, is still a challenge for current systems. While certain types of bulk iterative algorithms are supported by novel dataflow frameworks, these systems cannot exploit computational dependencies present in many algorithms, such as graph algorithms. As a result, these algorithms are inefficiently executed and have led to specialized systems based on other paradigms, such as message passing or shared memory.<\/jats:p>\n          <jats:p>\n            We propose a method to integrate\n            <jats:italic>incremental iterations<\/jats:italic>\n            , a form of workset iterations, with parallel dataflows. After showing how to integrate bulk iterations into a dataflow system and its optimizer, we present an extension to the programming model for incremental iterations. The extension alleviates for the lack of\n            <jats:italic>mutable state<\/jats:italic>\n            in dataflows and allows for exploiting the\n            <jats:italic>sparse computational dependencies<\/jats:italic>\n            inherent in many iterative algorithms. The evaluation of a prototypical implementation shows that those aspects lead to up to two orders of magnitude speedup in algorithm runtime, when exploited. In our experiments, the improved dataflow system is highly competitive with specialized systems while maintaining a transparent and unified dataflow abstraction.\n          <\/jats:p>","DOI":"10.14778\/2350229.2350245","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1268-1279","source":"Crossref","is-referenced-by-count":92,"title":["Spinning fast iterative data flows"],"prefix":"10.14778","volume":"5","author":[{"given":"Stephan","family":"Ewen","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kostas","family":"Tzoumas","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moritz","family":"Kaufmann","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Volker","family":"Markl","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516401"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951367"},{"key":"e_1_2_1_3_1","unstructured":"Apache Giraph. http:\/\/incubator.apache.org\/giraph\/.  Apache Giraph. http:\/\/incubator.apache.org\/giraph\/."},{"key":"e_1_2_1_4_1","unstructured":"Apache Hadoop. http:\/\/hadoop.apache.org.  Apache Hadoop. http:\/\/hadoop.apache.org."},{"key":"e_1_2_1_5_1","unstructured":"Apache Mahout. http:\/\/mahout.apache.org.  Apache Mahout. http:\/\/mahout.apache.org."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16859"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807148"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28689"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-011-7082-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767921"},{"key":"e_1_2_1_12_1","volume-title":"CoRR, abs\/1203.0160","author":"Bu Y.","year":"2012","unstructured":"Y. Bu , V. R. Borkar , M. J. Carey , J. Rosen , N. Polyzotis , T. Condie , M. Weimer , R. Ramakrishnan . Scaling Datalog for machine learning on Big Data . In CoRR, abs\/1203.0160 , 2012 . Y. Bu, V. R. Borkar, M. J. Carey, J. Rosen, N. Polyzotis, T. Condie, M. Weimer, R. Ramakrishnan. Scaling Datalog for machine learning on Big Data. In CoRR, abs\/1203.0160, 2012."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920881"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(88)90033-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454166"},{"key":"e_1_2_1_16_1","first-page":"137","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . MapReduce: Simplified data processing on large clusters . In OSDI , pp. 137 -- 150 , 2004 . J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI, pp. 137--150, 2004."},{"key":"e_1_2_1_17_1","first-page":"228","volume-title":"VLDB","author":"DeWitt D. J.","year":"1986","unstructured":"D. J. DeWitt , R. H. Gerber , G. Graefe , M. L. Heytens , K. B. Kumar , and M. Muralikrishna . GAMMA - A high performance dataflow database machine . In VLDB , pp. 228 -- 237 , 1986 . D. J. DeWitt, R. H. Gerber, G. Graefe, M. L. Heytens, K. B. Kumar, and M. Muralikrishna. GAMMA - A high performance dataflow database machine. In VLDB, pp. 228--237, 1986."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851476.1851593"},{"key":"e_1_2_1_19_1","first-page":"209","volume-title":"VLDB","author":"Fushimi S.","year":"1986","unstructured":"S. Fushimi , M. Kitsuregawa , and H. Tanaka . An overview of the system software of a parallel relational database machine GRACE . In VLDB , pp. 209 -- 219 , 1986 . S. Fushimi, M. Kitsuregawa, and H. Tanaka. An overview of the system software of a parallel relational database machine GRACE. In VLDB, pp. 209--219, 1986."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/645478.757691"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/645472.653378"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350244"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00290339"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.14"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1992.222991"},{"key":"e_1_2_1_28_1","first-page":"340","article-title":"GraphLab: A new framework for parallel machine learning","author":"Low Y.","year":"2010","unstructured":"Y. Low , J. Gonzalez , A. Kyrola , D. Bickson , C. Guestrin , and J. M. Hellerstein . GraphLab: A new framework for parallel machine learning . In UAI , pp. 340 -- 349 , 2010 . Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. GraphLab: A new framework for parallel machine learning. In UAI, pp. 340--349, 2010.","journal-title":"UAI"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_30_1","volume-title":"NSDI","author":"Murray D. G.","year":"2011","unstructured":"D. G. Murray , M. Schwarzkopf , C. Smowton , S. Smith , A. Madhavapeddy , and S. Hand . Ciel: A universal execution engine for distributed data-flow computing . In NSDI , 2011 . D. G. Murray, M. Schwarzkopf, C. Smowton, S. Smith, A. Madhavapeddy, and S. Hand. Ciel: A universal execution engine for distributed data-flow computing. In NSDI, 2011."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66937"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_34_1","volume-title":"Handbook of Theoretical Computer Science","author":"Valiant L. G.","year":"1990","unstructured":"L. G. Valiant . General purpose parallel architectures . In Handbook of Theoretical Computer Science , Volume A: Algorithms and Complexity (A), pp. 943-- 972 , 1990 . L. G. Valiant. General purpose parallel architectures. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), pp. 943--972, 1990."},{"key":"e_1_2_1_35_1","first-page":"389","article-title":"Machine learning in ScalOps, a higher order cloud computing language","volume":"9","author":"Weimer M.","year":"2011","unstructured":"M. Weimer , T. Condie , and R. Ramakrishnan . Machine learning in ScalOps, a higher order cloud computing language . In NIPS BigLearn , Vol. 9 , pp. 389 -- 396 , 2011 . M. Weimer, T. Condie, and R. Ramakrishnan. Machine learning in ScalOps, a higher order cloud computing language. In NIPS BigLearn, Vol. 9, pp. 389--396, 2011.","journal-title":"NIPS BigLearn"},{"key":"e_1_2_1_36_1","first-page":"1","volume-title":"HotCloud","author":"Zaharia M.","year":"2010","unstructured":"M. Zaharia , M. Chowdhury , M. J. Franklin , S. Shenker , and I. Stoica . Spark: Cluster computing with working sets . In HotCloud , pp. 1 -- 7 , 2010 . M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica. Spark: Cluster computing with working sets. In HotCloud, pp. 1--7, 2010."},{"key":"e_1_2_1_37_1","first-page":"2595","volume-title":"NIPS","author":"Zinkevich M.","year":"2010","unstructured":"M. Zinkevich , M. Weimer , A. J. Smola , and L. Li . Parallelized stochastic gradient descent . In NIPS , pp. 2595 -- 2603 , 2010 . M. Zinkevich, M. Weimer, A. J. Smola, and L. Li. Parallelized stochastic gradient descent. In NIPS, pp. 2595--2603, 2010."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350245","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:27:12Z","timestamp":1672226832000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":35,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350245"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350245","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}