{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T22:25:34Z","timestamp":1766269534624},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,4]]},"abstract":"<jats:p>\n            Motivated by performance optimization of large-scale graph processing systems that distribute the graph across multiple machines, we consider the balanced graph partitioning problem. Compared to most of the previous work, we study the\n            <jats:italic>multi-dimensional<\/jats:italic>\n            variant in which balance according to multiple weight functions is required. As we demonstrate by experimental evaluation, such multi-dimensional balance is essential for achieving performance improvements for typical distributed graph processing workloads.\n          <\/jats:p>\n          <jats:p>We propose a new scalable technique for the multidimensional balanced graph partitioning problem. It is based on applying randomized projected gradient descent to a non-convex continuous relaxation of the objective. We show how to implement the new algorithm efficiently in both theory and practice utilizing various approaches for the projection step. Experiments with large-scale graphs containing up to hundreds of billions of edges indicate that our algorithm has superior performance compared to the state of the art.<\/jats:p>","DOI":"10.14778\/3324301.3324307","type":"journal-article","created":{"date-parts":[[2019,6,24]],"date-time":"2019-06-24T13:43:16Z","timestamp":1561383796000},"page":"906-919","source":"Crossref","is-referenced-by-count":15,"title":["Multi-dimensional balanced graph partitioning via projected gradient descent"],"prefix":"10.14778","volume":"12","author":[{"given":"Dmitrii","family":"Avdiukhin","sequence":"first","affiliation":[{"name":"Indiana University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Pupyrev","sequence":"additional","affiliation":[{"name":"Facebook"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grigory","family":"Yaroslavtsev","sequence":"additional","affiliation":[{"name":"Indiana University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Dykstra's projection algorithm. https:\/\/en.wikipedia.org\/wiki\/Dykstra%27s_projection_algorithm. Accessed: 2019-02-13.  Dykstra's projection algorithm. https:\/\/en.wikipedia.org\/wiki\/Dykstra%27s_projection_algorithm. Accessed: 2019-02-13."},{"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","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236208"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54423-1_51"},{"key":"e_1_2_1_5_1","first-page":"81","volume-title":"Proceedings of the 29th Conference on Learning Theory, COLT 2016","author":"Anandkumar A.","year":"2016"},{"issue":"3","key":"e_1_2_1_6_1","first-page":"5","article-title":"Large-scale graph processing infrastructure on Hadoop","volume":"11","author":"Avery C.","year":"2011","journal-title":"Proceedings of the Hadoop Summit. Santa Clara"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835829"},{"key":"e_1_2_1_8_1","volume-title":"Nonlinear programming. Athena scientific Belmont","author":"Bertsekas D. P.","year":"1999"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118601181"},{"key":"e_1_2_1_10_1","volume-title":"Alternating projections","author":"Boyd S.","year":"2003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"Boyd S.","year":"2004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790265.2790268"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939862"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1983.10477029"},{"key":"e_1_2_1_16_1","first-page":"797","volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015","author":"Ge R.","year":"2015"},{"key":"e_1_2_1_17_1","volume-title":"Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016","author":"Ge R.","year":"2016"},{"key":"e_1_2_1_18_1","first-page":"2","volume-title":"OSDI","volume":"12","author":"Gonzalez J. E.","year":"2012"},{"key":"e_1_2_1_19_1","first-page":"599","volume-title":"Proceedings of the 11th USENIX conference on Operating Systems Design and Implementation","author":"Gonzalez J. E.","year":"2014"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2016.02.003"},{"key":"e_1_2_1_21_1","volume-title":"Dec.","author":"Jain P.","year":"2017"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137650"},{"key":"e_1_2_1_23_1","volume-title":"Metis - unstructured graph partitioning and sparse matrix ordering system, version 2.0. Technical report","author":"Karypis G.","year":"1995"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/509058.509086"},{"key":"e_1_2_1_25_1","volume-title":"An efficient heuristic procedure for partitioning graphs. Bell system technical journal, 49(2):291--307","author":"Kernighan B. W.","year":"1970"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496872"},{"key":"e_1_2_1_27_1","volume-title":"Advances in Neural Information Processing Systems 23:  24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6--9","author":"Lee J. D.","year":"2010"},{"key":"e_1_2_1_28_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014.  J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3084451"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_31_1","volume-title":"An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in r n. Journal of optimization theory and applications, 117(3):553--574","author":"Maculan N.","year":"2003"},{"key":"e_1_2_1_32_1","first-page":"812","volume-title":"41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8--11, 2014, Proceedings, Part I","author":"Makarychev K.","year":"2014"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.153"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_30"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487696"},{"key":"e_1_2_1_36_1","volume-title":"4th IEEE International Conference on Pervasive Computing and Communications (PerCom 2006","author":"Ou S.","year":"2006"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48311-X_42"},{"key":"e_1_2_1_38_1","first-page":"455","volume-title":"Proceedings of the 13th Usenix Conference on Networked Systems Design and Implementation","author":"Shalita A.","year":"2016"},{"key":"e_1_2_1_39_1","volume-title":"When are nonconvex problems not scary? CoRR, abs\/1510.06096","author":"Sun J.","year":"2015"},{"key":"e_1_2_1_40_1","volume-title":"VEBO: A vertex-and edge-balanced ordering heuristic to load balance parallel graph processing. arXiv preprint arXiv:1806.06576","author":"Sun J.","year":"2018"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433461"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055543"},{"key":"e_1_2_1_44_1","volume-title":"Numerical optimization","author":"Wright S.","year":"1999"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3324301.3324307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:06:11Z","timestamp":1672221971000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3324301.3324307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4]]},"references-count":44,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["10.14778\/3324301.3324307"],"URL":"https:\/\/doi.org\/10.14778\/3324301.3324307","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,4]]}}}