{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T11:10:29Z","timestamp":1780485029817,"version":"3.54.1"},"reference-count":29,"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>\n            Multi-way Theta-join queries are powerful in describing complex relations and therefore widely employed in real practices. However, existing solutions from traditional distributed and parallel databases for multi-way Theta-join queries cannot be easily extended to fit a shared-nothing distributed computing paradigm, which is proven to be able to support OLAP applications over immense data volumes. In this work, we study the problem of efficient processing of multi-way Theta-join queries using MapReduce from a cost-effective perspective. Although there have been some works using the (\n            <jats:italic>key, value<\/jats:italic>\n            ) pair-based programming model to support join operations, efficient processing of multi-way Theta-join queries has never been fully explored. The substantial challenge lies in, given a number of processing units (that can run Map or Reduce tasks), mapping a multi-way Theta-join query to a number of MapReduce jobs and having them executed in a well scheduled sequence, such that the total processing time span is minimized. Our solution mainly includes two parts: 1) cost metrics for both single MapReduce job and a number of MapReduce jobs executed in a certain order; 2) the efficient execution of a chain-typed Theta-join with only one MapReduce job. Comparing with the query evaluation strategy proposed in [23] and the widely adopted Pig Latin and Hive SQL solutions, our method achieves significant improvement of the join processing efficiency.\n          <\/jats:p>","DOI":"10.14778\/2350229.2350238","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1184-1195","source":"Crossref","is-referenced-by-count":65,"title":["Efficient multi-way theta-join processing using MapReduce"],"prefix":"10.14778","volume":"5","author":[{"given":"Xiaofei","family":"Zhang","sequence":"first","affiliation":[{"name":"HKUST, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"HKUST, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Min","family":"Wang","sequence":"additional","affiliation":[{"name":"HP Labs China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Transaction processing performance council. http:\/\/www.tpc.org\/.  Transaction processing performance council. http:\/\/www.tpc.org\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.47"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453960"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807148"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989438"},{"key":"e_1_2_1_6_1","volume-title":"Note on counting eulerian circuits. CoRR, cs.CC\/0405067","author":"Brightwell G.","year":"2004","unstructured":"G. Brightwell and Note on counting eulerian circuits. CoRR, cs.CC\/0405067 , 2004 . G. Brightwell and et al. Note on counting eulerian circuits. CoRR, cs.CC\/0405067, 2004."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767881"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153856"},{"key":"e_1_2_1_9_1","first-page":"313","volume-title":"NSDI","author":"Condie T.","year":"2010","unstructured":"T. Condie and et al. Mapreduce online . In NSDI , pages 313 -- 328 , 2010 . T. Condie and et al. Mapreduce online. In NSDI, pages 313--328, 2010."},{"key":"e_1_2_1_10_1","volume-title":"Introduction to Algorithms (3. ed.)","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen and Introduction to Algorithms (3. ed.) . MIT Press , 2009 . T. H. Cormen and et al. Introduction to Algorithms (3. ed.). MIT Press, 2009."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807157"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"issue":"1","key":"e_1_2_1_13_1","first-page":"518","article-title":"Hadoop++: Making a yellow elephant run like a cheetah (without it even noticing)","volume":"3","author":"Dittrich J.","year":"2010","unstructured":"J. Dittrich and . Hadoop++: Making a yellow elephant run like a cheetah (without it even noticing) . PVLDB , 3 ( 1 ): 518 -- 529 , 2010 . J. Dittrich and et al. Hadoop++: Making a yellow elephant run like a cheetah (without it even noticing). PVLDB, 3(1):518--529, 2010.","journal-title":"PVLDB"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_15_1","volume-title":"Calculus of Variations","author":"Gelfand I.","year":"2000","unstructured":"I. Gelfand and Calculus of Variations . Dover Publ ., 2000 . I. Gelfand and et al. Calculus of Variations. Dover Publ., 2000."},{"key":"e_1_2_1_16_1","volume-title":"Algorithmic Graph Theory","author":"Gibbons A.","year":"1985","unstructured":"A. Gibbons . Algorithmic Graph Theory . Cambridge University Press , 1985 . A. Gibbons. Algorithmic Graph Theory. Cambridge University Press, 1985."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767933"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2011.66"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1078-6"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790423","volume-title":"Probability theory: The logic of science","author":"Jaynes E. T.","year":"2003","unstructured":"E. T. Jaynes . Probability theory: The logic of science . Cambridge University Press , Cambridge , 2003 . E. T. Jaynes. Probability theory: The logic of science. Cambridge University Press, Cambridge, 2003."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920903"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.917567"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.26"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920906"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989423"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/141356.141392"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807222"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038928"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447802"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:26:02Z","timestamp":1672226762000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":29,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350238"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350238","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}