{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T16:01:11Z","timestamp":1778601671106,"version":"3.51.4"},"reference-count":48,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T00:00:00Z","timestamp":1565395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Balanced partitioning is often a crucial first step in solving large-scale graph optimization problems, for example, in some cases, a big graph can be chopped into pieces that fit on one machine to be processed independently before stitching the results together, leading to certain suboptimality from the interaction among different pieces. In other cases, links between different parts may show up in the running time and\/or network communications cost, hence the desire to have small cut size. We study a distributed balanced-partitioning problem where the goal is to partition the vertices of a given graph into k pieces so as to minimize the total cut size. Our algorithm is composed of a few steps that are easily implementable in distributed computation frameworks such as MapReduce. The algorithm first embeds nodes of the graph onto a line, and then processes nodes in a distributed manner guided by the linear embedding order. We examine various ways to find the first embedding, for example, via a hierarchical clustering or Hilbert curves. Then we apply four different techniques including local swaps, and minimum cuts on the boundaries of partitions, as well as contraction and dynamic programming. As our empirical study, we compare the above techniques with each other, and also to previous work in distributed graph algorithms, for example, a label-propagation method, FENNEL and Spinner. We report our results both on a private map graph and several public social networks, and show that our results beat previous distributed algorithms: For instance, compared to the label-propagation algorithm, we report an improvement of 15\u201325% in the cut value. We also observe that our algorithms admit scalable distributed implementation for any number of partitions. Finally, we explain three applications of this work at Google: (1) Balanced partitioning is used to route multi-term queries to different replicas in Google Search backend in a way that reduces the cache miss rates by \u2248    0.5 %    , which leads to a double-digit gain in throughput of production clusters. (2) Applied to the Google Maps Driving Directions, balanced partitioning minimizes the number of cross-shard queries with the goal of saving in CPU usage. This system achieves load balancing by dividing the world graph into several \u201cshards\u201d. Live experiments demonstrate an \u2248    40 %     drop in the number of cross-shard queries when compared to a standard geography-based method. (3) In a job scheduling problem for our data centers, we use balanced partitioning to evenly distribute the work while minimizing the amount of communication across geographically distant servers. In fact, the hierarchical nature of our solution goes well with the layering of data center servers, where certain machines are closer to each other and have faster links to one another.<\/jats:p>","DOI":"10.3390\/a12080162","type":"journal-article","created":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T06:38:02Z","timestamp":1565591882000},"page":"162","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Distributed Balanced Partitioning via Linear Embedding \u2020"],"prefix":"10.3390","volume":"12","author":[{"given":"Kevin","family":"Aydin","sequence":"first","affiliation":[{"name":"Google Research, 76 Ninth Ave, New York, NY 10011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MohammadHossein","family":"Bateni","sequence":"additional","affiliation":[{"name":"Google Research, 76 Ninth Ave, New York, NY 10011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google Research, 76 Ninth Ave, New York, NY 10011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,8,10]]},"reference":[{"key":"ref_1","unstructured":"Dongarra, J., Foster, I., Fox, G., Gropp, W., Kennedy, K., Torczon, L., and White, A. (2003). The Sourcebook of Parallel Computing, Morgan Kaufmann Publishers Inc."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1007\/s00224-006-1350-7","article-title":"Balanced Graph Partitioning","volume":"39","author":"Andreev","year":"2006","journal-title":"Theory Comput. Syst."},{"key":"ref_3","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Ugander, J., and Backstrom, L. (2013, January 4\u20138). Balanced label propagation for partitioning massive graphs. Proceedings of the Sixth ACM International Conference on Web Search and Data Mining (WSDM \u201913), Rome, Italy.","DOI":"10.1145\/2433396.2433461"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E., Gkantsidis, C., Radunovic, B., and Vojnovic, M. (2014, January 24\u201328). FENNEL: Streaming graph partitioning for massive scale graphs. Proceedings of the Seventh ACM International Conference on Web Search and Data Mining (WSDM 2014), New York, NY, USA.","DOI":"10.1145\/2556195.2556213"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., and Werneck, R.F.F. (2011, January 16\u201320). Graph Partitioning with Natural Cuts. Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2011), Anchorage, AK, USA.","DOI":"10.1109\/IPDPS.2011.108"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., and Werneck, R.F.F. (2012, January 16). Exact Combinatorial Branch-and-Bound for Graph Bisection. Proceedings of the 14th Meeting on Algorithm Engineering & Experiments (ALENEX 2012), Kyoto, Japan.","DOI":"10.1137\/1.9781611972924.3"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., and Czajkowski, G. (2010, January 6\u201310). Pregel: A system for large-scale graph processing. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201910), Indianapolis, IN, USA.","DOI":"10.1145\/1807167.1807184"},{"key":"ref_9","unstructured":"Ching, A., and Kunz, C. (2019, August 08). Giraph: Large-Scale Graph Processing on Hadoop. Available online: https:\/\/www.youtube.com\/watch?v=l4nQjAG6fac."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kang, U., Tsourakakis, C.E., and Faloutsos, C. (2009, January 6\u20139). PEGASUS: A Peta-Scale Graph Mining System. Proceedings of the Ninth IEEE International Conference on Data Mining (ICDM 2009), Miami, FL, USA.","DOI":"10.1109\/ICDM.2009.14"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Stanton, I. (2014, January 5\u20137). Streaming Balanced Graph Partitioning Algorithms for Random Graphs. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR, USA.","DOI":"10.1137\/1.9781611973402.95"},{"key":"ref_12","unstructured":"Dean, J., and Ghemawat, S. (2004, January 6\u20138). MapReduce: Simplified Data Processing on Large Clusters. Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI), San Francisco, CA, USA."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Aydin, K., Bateni, M., and Mirrokni, V.S. (2016, January 22\u201325). Distributed Balanced Partitioning via Linear Embedding. Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, San Francisco, CA, USA.","DOI":"10.1145\/2835776.2835829"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Eckles, D., Karrer, B., and Ugander, J. (2017). Design and analysis of experiments in networks: Reducing bias from interference. J. Causal Inference, 5.","DOI":"10.1515\/jci-2015-0021"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Pouget-Abadie, J., Mirrokni, V., Parkes, D.C., and Airoldi, E.M. (2018, January 19\u201323). Optimizing Cluster-based Randomized Experiments Under Monotonicity. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD \u201918), London, UK.","DOI":"10.1145\/3219819.3220067"},{"key":"ref_16","unstructured":"Boldi, P., Rosa, M., Santini, M., and Vigna, S. (April, January 28). Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. Proceedings of the 20th International Conference on World Wide Web (WWW \u201911), Hyderabad, India."},{"key":"ref_17","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., and Raghavan, P. (July, January 28). On compressing social networks. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201909 ), Paris, France."},{"key":"ref_18","unstructured":"Tsourakakis, C.E., Kolountzakis, M.N., and Miller, G.L. (2009). Approximate Triangle Counting. arXiv."},{"key":"ref_19","unstructured":"Martella, C., Logothetis, D., and Siganos, G. (2014). Spinner: Scalable Graph Partitioning for the Cloud. arXiv."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs","volume":"20","author":"Karypis","year":"1998","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Stanton, I., and Kliot, G. (2012, January 12\u201316). Streaming graph partitioning for large distributed graphs. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201912), Beijing, China.","DOI":"10.1145\/2339530.2339722"},{"key":"ref_22","first-page":"1981","article-title":"Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs","volume":"7","author":"Yan","year":"2014","journal-title":"PVLDB"},{"key":"ref_23","unstructured":"Aydin, K., Bateni, M., and Mirrokni, V. (2019, August 08). Public Data for Balanced Partioning Paper. Available online: http:\/\/goo.gl\/okvwpa."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Goldschmidt, O., and Hochbaum, D.S. (1988, January 24\u201326). Polynomial Algorithm for the k-Cut Problem. Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS 1988), White Plains, NY, USA.","DOI":"10.1109\/SFCS.1988.21960"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1137\/S0097539701387660","article-title":"A Polylogarithmic Approximation of the Minimum Bisection","volume":"31","author":"Feige","year":"2002","journal-title":"SIAM J. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Ene, A., Im, S., and Moseley, B. (2011, January 21\u201324). Fast clustering using MapReduce. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201911), San Diego, CA, USA.","DOI":"10.1145\/2020408.2020515"},{"key":"ref_27","first-page":"622","article-title":"Scalable K-Means++","volume":"5","author":"Bahmani","year":"2012","journal-title":"PVLDB"},{"key":"ref_28","unstructured":"Balcan, M.F., Ehrlich, S., and Liang, Y. (2013, January 5\u201310). Distributed k-means and k-median clustering on general communication topologies. Proceedings of the NIPS, Lake Tahoe, NV, USA."},{"key":"ref_29","unstructured":"Bateni, M., Bhaskara, A., Lattanzi, S., and Mirrokni, V. (2014, January 8\u201313). Distributed Balanced Clustering via Mapping Coresets. Proceedings of the Advances in Neural Information Processing Systems 27: 28th Annual Conference on Neural Information Processing Systems 2014, Montreal, QC, Canada."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Strongin, R.G., and Sergeyev, Y.D. (2000). Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms. Nonconvex Optimization and Its Applications, Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-4677-1"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"2001","DOI":"10.1109\/69.908985","article-title":"Analysis of the clustering properties of the Hilbert space-filling curve","volume":"13","author":"Moon","year":"2001","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1109\/83.499920","article-title":"On the metric properties of discrete space-filling curves","volume":"5","author":"Gotsman","year":"1996","journal-title":"IEEE Trans. Image Process."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0166-218X(00)00326-7","article-title":"Towards optimal locality in mesh-indexings","volume":"117","author":"Niedermeier","year":"2002","journal-title":"Discret. Appl. Math."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0012-365X(99)00173-9","article-title":"Optimal linear arrangement of a rectangular grid","volume":"213","author":"Fishburn","year":"2000","journal-title":"Discret. Math."},{"key":"ref_35","first-page":"1409","article-title":"A statistical method for evaluating systematic relationships","volume":"38","author":"Sokal","year":"1958","journal-title":"Univ. Kans. Sci. Bull."},{"key":"ref_36","first-page":"153","article-title":"P\u0159\u00edsp\u011bvek k \u0159e\u0161en\u00ed ot\u00e1zky ekonomick\u00e9 stavby elektrovodn\u00edch s\u00edt\u00ed (Contribution to the solution of a problem of economical construction of electrical networks)","volume":"15","year":"1926","journal-title":"Elektron. Obz."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Rastogi, V., Machanavajjhala, A., Chitnis, L., and Sarma, A.D. (2013, January 8\u201312). Finding connected components in map-reduce in logarithmic rounds. Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE 2013), Brisbane, QLD, Australia.","DOI":"10.1109\/ICDE.2013.6544813"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Kiveris, R., Lattanzi, S., Mirrokni, V., Rastogi, V., and Vassilvitskii, S. (2014, January 3\u20135). Connected Components in MapReduce and Beyond. Proceedings of the Fifth ACM Symposium on Cloud Computing, SOCC 2014, Seattle, WA, USA.","DOI":"10.1145\/2670979.2670997"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1137\/S0097539702413197","article-title":"New Approximation Techniques for Some Linear Ordering Problems","volume":"34","author":"Rao","year":"2004","journal-title":"SIAM J. Comput."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.ipl.2006.07.009","article-title":"An improved approximation ratio for the minimum linear arrangement problem","volume":"101","author":"Feige","year":"2007","journal-title":"Inf. Process. Lett."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/s00453-008-9191-1","article-title":"l22 Spreading Metrics Vertex Ordering Probl","volume":"56","author":"Charikar","year":"2010","journal-title":"Algorithmica"},{"key":"ref_42","unstructured":"Bateni, M., Behnezhad, S., Derakhshan, M., Hajiaghayi, M., Kiveris, R., Lattanzi, S., and Mirrokni, V.S. (2017, January 4\u20139). Affinity Clustering: Hierarchical Clustering at Scale. Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, Long Beach, CA, USA."},{"key":"ref_43","unstructured":"Aydin, K., and Bateni, M. (2019, August 08). Balanced Partitioning and Hierarchical Clustering at Scale. Available online: https:\/\/ai.googleblog.com\/2018\/03\/balanced-partitioning-and-hierarchical.html."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Kwak, H., Lee, C., Park, H., and Moon, S. (2010, January 26\u201330). What is Twitter, a social network or a news media?. Proceedings of the 19th International Conference on World Wide Web (WWW \u201910), Raleigh, NC, USA.","DOI":"10.1145\/1772690.1772751"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Yang, J., and Leskovec, J. (2012, January 10\u201313). Defining and Evaluating Network Communities Based on Ground-Truth. Proceedings of the 12th IEEE International Conference on Data Mining (ICDM 2012), Brussels, Belgium.","DOI":"10.1109\/ICDM.2012.138"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., and Faloutsos, C. (2004, January 22\u201324). R-MAT: A Recursive Model for Graph Mining. Proceedings of the Fourth SIAM International Conference on Data Mining, Lake Buena Vista, FL, USA.","DOI":"10.1137\/1.9781611972740.43"},{"key":"ref_47","first-page":"709","article-title":"Cache-aware load balancing of data center applications","volume":"12","author":"Archer","year":"2019","journal-title":"PVLDB"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Rolnick, D., Aydin, K., Pouget-Abadie, J., Kamali, S., Mirrokni, V., and Najmi, A. (2019, January 4\u20138). Randomized Experimental Design via Geographic Clustering. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, AK, USA.","DOI":"10.1145\/3292500.3330778"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/162\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:10:08Z","timestamp":1760188208000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,10]]},"references-count":48,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2019,8]]}},"alternative-id":["a12080162"],"URL":"https:\/\/doi.org\/10.3390\/a12080162","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,10]]}}}