{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T11:34:07Z","timestamp":1753356847414},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>We propose OptIQ, a query optimization approach for iterative queries in distributed environment. OptIQ removes redundant computations among different iterations by extending the traditional techniques of view materialization and incremental view evaluation. First, OptIQ decomposes iterative queries into invariant and variant views, and materializes the former view. Redundant computations are removed by reusing the materialized view among iterations. Second, OptIQ incrementally evaluates the variant view, so that redundant computations are removed by skipping the evaluation on converged tuples in the variant view. We verify the effectiveness of OptIQ through the queries of PageRank and k-means clustering on real datasets. The results show that OptIQ achieves high efficiency, up to five times faster than is possible without removing the redundant computations among iterations.<\/jats:p>","DOI":"10.14778\/2732240.2732243","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"241-252","source":"Crossref","is-referenced-by-count":11,"title":["Optimization for iterative queries on MapReduce"],"prefix":"10.14778","volume":"7","author":[{"given":"Makoto","family":"Onizuka","sequence":"first","affiliation":[{"name":"NTT Software Innovation Center"}]},{"given":"Hiroyuki","family":"Kato","sequence":"additional","affiliation":[{"name":"National Institute of Informatics"}]},{"given":"Soichiro","family":"Hidaka","sequence":"additional","affiliation":[{"name":"National Institute of Informatics"}]},{"given":"Keisuke","family":"Nakano","sequence":"additional","affiliation":[{"name":"University of Electro-Communications"}]},{"given":"Zhenjiang","family":"Hu","sequence":"additional","affiliation":[{"name":"National Institute of Informatics"}]}],"member":"320","published-online":{"date-parts":[[2013,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687731"},{"key":"e_1_2_1_2_1","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho A. V.","year":"2006","unstructured":"A. V. Aho , M. S. Lam , R. Sethi , and J. D. Ullman . Compilers: Principles, Techniques, and Tools ( 2 nd Edition). Addison-Wesley Longman Publishing Co., Inc. , 2006 . A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley Longman Publishing Co., Inc., 2006.","edition":"2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920881"},{"key":"e_1_2_1_4_1","first-page":"137","volume-title":"Proc. OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . MapReduce: Simplified data processing on large clusters . In Proc. OSDI , pages 137 -- 150 , 2004 . J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In Proc. OSDI, pages 137--150, 2004."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629175.1629198"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851476.1851593"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247601"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687568"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170066"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807139"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.12.008"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.14"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_1_14_1","first-page":"556","volume-title":"In NIPS","author":"Lee D. D.","year":"2001","unstructured":"D. D. Lee and H. S. Seung . Algorithms for non-negative matrix factorization . In In NIPS , pages 556 -- 562 , 2001 . D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In In NIPS, pages 556--562, 2001."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.26"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855013"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350246"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376726"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687569"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559865"},{"key":"e_1_2_1_23_1","volume-title":"Cloud Futures 2011 workshop, 06\/2011","author":"Qiu J.","year":"2011","unstructured":"J. Qiu , T. Gunarathne , and G. Fox . Classical and iterative mapreduce on AzureClassical and iterative MapReduce on Azure . In Cloud Futures 2011 workshop, 06\/2011 2011 . J. Qiu, T. Gunarathne, and G. Fox. Classical and iterative mapreduce on AzureClassical and iterative MapReduce on Azure. In Cloud Futures 2011 workshop, 06\/2011 2011."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367563"},{"key":"e_1_2_1_25_1","first-page":"281","volume-title":"Proc. NIPS","author":"Chu C.","year":"2007","unstructured":"C. tao Chu , S. K. Kim , Y. an Lin , Y. Yu , G. Bradski , A. Y. Ng , and K. Olukotun . Map-reduce for machine learning on multicore . In Proc. NIPS , pages 281 -- 288 , 2007 . C. tao Chu, S. K. Kim, Y. an Lin, Y. Yu, G. Bradski, A. Y. Ng, and K. Olukotun. Map-reduce for machine learning on multicore. In Proc. NIPS, pages 281--288, 2007."},{"key":"e_1_2_1_26_1","unstructured":"The Apache Software Foundation. Mahout. http:\/\/mahout.apache.org.  The Apache Software Foundation. Mahout. http:\/\/mahout.apache.org."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447738"},{"key":"e_1_2_1_28_1","first-page":"2","volume-title":"Proc. NSDI","author":"Zaharia M.","year":"2012","unstructured":"M. Zaharia , M. Chowdhury , T. Das , A. Dave , J. Ma , M. McCauley , M. J. Franklin , S. Shenker , and I. Stoica . Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing . In Proc. NSDI , pages 2 -- 2 , 2012 . M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker, and I. Stoica. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing. In Proc. NSDI, pages 2--2, 2012."},{"key":"e_1_2_1_29_1","first-page":"10","volume-title":"Proc. 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 Proc. HotCloud , pages 10 -- 10 , 2010 . M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica. Spark: cluster computing with working sets. In Proc. HotCloud, pages 10--10, 2010."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.260"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732240.2732243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:46:30Z","timestamp":1672224390000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732240.2732243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.14778\/2732240.2732243"],"URL":"https:\/\/doi.org\/10.14778\/2732240.2732243","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}