{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T08:47:50Z","timestamp":1780390070864,"version":"3.54.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>\n            We design and implement a distributed algorithm for balanced\n            <jats:italic>k<\/jats:italic>\n            -way hypergraph partitioning that minimizes fanout, a fundamental hypergraph quantity also known as the communication volume and (\n            <jats:italic>k<\/jats:italic>\n            - 1)-cut metric, by optimizing a novel objective called\n            <jats:italic>probabilistic fanout.<\/jats:italic>\n            This choice allows a simple local search heuristic to achieve comparable solution quality to the best existing hypergraph partitioners.\n          <\/jats:p>\n          <jats:p>Our algorithm is arbitrarily scalable due to a careful design that controls computational complexity, space complexity, and communication. In practice, we commonly process hypergraphs with billions of vertices and hyperedges in a few hours. We explain how the algorithm's scalability, both in terms of hypergraph size and bucket count, is limited only by the number of machines available. We perform an extensive comparison to existing distributed hypergraph partitioners and find that our approach is able to optimize hypergraphs roughly 100 times bigger on the same set of machines.<\/jats:p>\n          <jats:p>\n            We call the resulting tool\n            <jats:italic>Social Hash Partitioner<\/jats:italic>\n            , and accompanying this paper, we open-source the most scalable version based on recursive bisection.\n          <\/jats:p>","DOI":"10.14778\/3137628.3137650","type":"journal-article","created":{"date-parts":[[2017,9,7]],"date-time":"2017-09-07T13:35:53Z","timestamp":1504791353000},"page":"1418-1429","source":"Crossref","is-referenced-by-count":45,"title":["Social hash partitioner"],"prefix":"10.14778","volume":"10","author":[{"given":"Igor","family":"Kabiljo","sequence":"first","affiliation":[{"name":"Facebook"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brian","family":"Karrer","sequence":"additional","affiliation":[{"name":"Facebook"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mayank","family":"Pundir","sequence":"additional","affiliation":[{"name":"Facebook"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergey","family":"Pupyrev","sequence":"additional","affiliation":[{"name":"Facebook"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alon","family":"Shalita","sequence":"additional","affiliation":[{"name":"Facebook"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Social Hash Partitioner. https:\/\/issues.apache.org\/jira\/browse\/GIRAPH-1131.  Social Hash Partitioner. https:\/\/issues.apache.org\/jira\/browse\/GIRAPH-1131."},{"key":"e_1_2_1_2_1","unstructured":"Apache Giraph. http:\/\/giraph.apache.org\/.  Apache Giraph. http:\/\/giraph.apache.org\/."},{"key":"e_1_2_1_3_1","unstructured":"Stanford large network dataset collection. https:\/\/snap.stanford.edu\/data.  Stanford large network dataset collection. https:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/APCAS.1996.569275"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(95)00008-4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1350-7"},{"key":"e_1_2_1_7_1","first-page":"588","article-title":"Graph partitioning and graph clustering, 10th DIMACS implementation challenge workshop","author":"Bader D. A.","year":"2013","journal-title":"Contemporary Mathematics"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118601181"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920853"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2408776.2408794"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.12.002"},{"key":"e_1_2_1_14_1","first-page":"10","volume-title":"International Parallel & Distributed Processing Symposium","author":"Devine K. D."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939862"},{"key":"e_1_2_1_16_1","unstructured":"S. Edunov D. Logothetis C. Wang A. Ching and M. Kabiljo. Darwini: Generating realistic large-scale social graphs. arXiv:1610.00664 2016.  S. Edunov D. Logothetis C. Wang A. Ching and M. Kabiljo. Darwini: Generating realistic large-scale social graphs. arXiv:1610.00664 2016."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9802-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/800263.809204"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2618243.2618258"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.748202"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1155\/2000\/19436"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell system technical journal 49(2):291--307 1970.  B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell system technical journal 49(2):291--307 1970.","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"e_1_2_1_24_1","unstructured":"T. Kiefer. Allocation Strategies for Data-Oriented Architectures. PhD thesis Dresden Technische Universit\u00e4t Dresden 2016.  T. Kiefer. Allocation Strategies for Data-Oriented Architectures. PhD thesis Dresden Technische Universit\u00e4t Dresden 2016."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496872"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0362-1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.1990.112608"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.01.004"},{"key":"e_1_2_1_29_1","first-page":"455","volume-title":"NSDI","author":"Shalita A.","year":"2016"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827593255135"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.11.002"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49178-3_36"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3137628.3137650","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:55:55Z","timestamp":1672221355000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3137628.3137650"}},"subtitle":["a scalable distributed hypergraph partitioner"],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":33,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.14778\/3137628.3137650"],"URL":"https:\/\/doi.org\/10.14778\/3137628.3137650","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}