{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:12:53Z","timestamp":1789434773521,"version":"build-2803163510"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,6]]},"abstract":"<jats:p>\n            In distributed query processing, data shuffle is one of the most costly operations. We examined scaling limitations to data shuffle that current systems and the research literature do not solve. As the number of input and output partitions increases, na\u00efve shuffling will result in high\n            <jats:italic>fan-out<\/jats:italic>\n            and\n            <jats:italic>fan-in.<\/jats:italic>\n            There are practical limits to\n            <jats:italic>fan-out,<\/jats:italic>\n            as a consequence of limits on memory buffers, network ports and I\/O handles. There are practical limits to\n            <jats:italic>fan-in<\/jats:italic>\n            because it multiplies the communication errors due to faults in commodity clusters impeding progress. Existing solutions that limit\n            <jats:italic>fan-out<\/jats:italic>\n            and\n            <jats:italic>fan-in<\/jats:italic>\n            do so at the cost of scaling quadratically in the number of nodes in the data flow graph. This dominates the costs of shuffling large datasets.\n          <\/jats:p>\n          <jats:p>\n            We propose a novel algorithm called Hyper Dimension Shuffle that we have introduced in production in SCOPE, Microsoft's internal big data analytics system. Hyper Dimension Shuffle is inspired by the divide and conquer concept, and utilizes a recursive partitioner with intermediate aggregations. It yields\n            <jats:italic>quasilinear<\/jats:italic>\n            complexity of the shuffling graph with tight guarantees on\n            <jats:italic>fan-out<\/jats:italic>\n            and\n            <jats:italic>fan-in.<\/jats:italic>\n            We demonstrate how it avoids the shuffling graph blow-up of previous algorithms to shuffle at petabyte-scale efficiently on both synthetic benchmarks and real applications.\n          <\/jats:p>","DOI":"10.14778\/3339490.3339495","type":"journal-article","created":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:50:07Z","timestamp":1565182207000},"page":"1113-1125","source":"Crossref","is-referenced-by-count":14,"title":["Hyper dimension shuffle"],"prefix":"10.14778","volume":"12","author":[{"given":"Shi","family":"Qiao","sequence":"first","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adrian","family":"Nicoara","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jin","family":"Sun","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"Friedman","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hiren","family":"Patel","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jaliya","family":"Ekanayake","sequence":"additional","affiliation":[{"name":"Microsoft Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Hadoop. https:\/\/hadoop.apache.org\/.  Apache Hadoop. https:\/\/hadoop.apache.org\/."},{"key":"e_1_2_1_2_1","unstructured":"Apache Spark. https:\/\/spark.apache.org\/.  Apache Spark. https:\/\/spark.apache.org\/."},{"key":"e_1_2_1_3_1","unstructured":"Apache Tez. https:\/\/tez.apache.org\/.  Apache Tez. https:\/\/tez.apache.org\/."},{"key":"e_1_2_1_4_1","unstructured":"Hadoop distributed filesystem. http:\/\/hadoop.apache.org\/hdfs.  Hadoop distributed filesystem. http:\/\/hadoop.apache.org\/hdfs."},{"key":"e_1_2_1_5_1","unstructured":"Kosmos distributed filesystem. http:\/\/kosmosfs.sourceforge.net\/.  Kosmos distributed filesystem. http:\/\/kosmosfs.sourceforge.net\/."},{"key":"e_1_2_1_6_1","unstructured":"TPC-H specification. http:\/\/www.tpc.org\/tpc_documents_current_versions\/pdf\/tpc-h_v2.17.3.pdf.  TPC-H specification. http:\/\/www.tpc.org\/tpc_documents_current_versions\/pdf\/tpc-h_v2.17.3.pdf."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687731"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367533"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824080"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33500-6_4"},{"key":"e_1_2_1_12_1","first-page":"285","volume-title":"Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, OSDI'14","author":"Boutin E.","year":"2014","unstructured":"E. Boutin , J. Ekanayake , W. Lin , B. Shi , J. Zhou , Z. Qian , M. Wu , and L. Zhou . Apollo: Scalable and coordinated scheduling for cloud-scale computing . In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, OSDI'14 , pages 285 -- 300 , Berkeley, CA, USA , 2014 . USENIX Association. E. Boutin, J. Ekanayake, W. Lin, B. Shi, J. Zhou, Z. Qian, M. Wu, and L. Zhou. Apollo: Scalable and coordinated scheduling for cloud-scale computing. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, OSDI'14, pages 285--300, Berkeley, CA, USA, 2014. USENIX Association."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454166"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007328.3007329"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_1_17_1","first-page":"10","volume-title":"Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation -","volume":"6","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . Mapreduce: Simplified data processing on large clusters . In Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation - Volume 6 , OSDI'04, pages 10 -- 10 , Berkeley, CA, USA , 2004 . USENIX Association. J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. In Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation - Volume 6, OSDI'04, pages 10--10, Berkeley, CA, USA, 2004. USENIX Association."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920908"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213934"},{"key":"e_1_2_1_20_1","first-page":"18","article-title":"The cascades framework for query optimization","author":"Graefe G.","year":"1995","unstructured":"G. Graefe . The cascades framework for query optimization . Data Engineering Bulletin , 18 , 1995 . G. Graefe. The cascades framework for query optimization. Data Engineering Bulletin, 18, 1995.","journal-title":"Data Engineering Bulletin"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389044"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190656"},{"key":"e_1_2_1_24_1","volume-title":"CIDR","author":"Li Y.","year":"2013","unstructured":"Y. Li , I. Pandis , R. M\u00fcller , V. Raman , and G. M. Lohman . Numa-aware algorithms: the case of data shuffling . In CIDR , 2013 . Y. Li, I. Pandis, R. M\u00fcller, V. Raman, and G. M. Lohman. Numa-aware algorithms: the case of data shuffling. In CIDR, 2013."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391233"},{"key":"e_1_2_1_26_1","first-page":"2","volume-title":"Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, NSDI'12","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 Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, NSDI'12 , pages 2 -- 2 , Berkeley, CA, USA , 2012 . USENIX Association. 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 Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, NSDI'12, pages 2--2, Berkeley, CA, USA, 2012. USENIX Association."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522737"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190534"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0280-z"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3339490.3339495","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:26:07Z","timestamp":1672223167000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3339490.3339495"}},"subtitle":["efficient data repartition at petabyte scale in SCOPE"],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":28,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["10.14778\/3339490.3339495"],"URL":"https:\/\/doi.org\/10.14778\/3339490.3339495","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,6]]}}}