{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:08:10Z","timestamp":1775912890027,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>Graph partitioning is an essential yet challenging task for massive graph analysis in distributed computing. Common graph partitioning methods scan the complete graph to obtain structural characteristics offline, before partitioning. However, the emerging need for low-latency, continuous graph analysis led to the development of online partitioning methods. Online methods ingest edges or vertices as a stream, making partitioning decisions on the fly based on partial knowledge of the graph. Prior studies have compared offline graph partitioning techniques across different systems. Yet, little effort has been put into investigating the characteristics of online graph partitioning strategies.<\/jats:p>\n          <jats:p>In this work, we describe and categorize online graph partitioning techniques based on their assumptions, objectives and costs. Furthermore, we employ an experimental comparison across different applications and datasets, using a unified distributed runtime based on Apache Flink. Our experimental results showcase that model-dependent online partitioning techniques such as low-cut algorithms offer better performance for communication-intensive applications such as bulk synchronous iterative algorithms, albeit higher partitioning costs. Otherwise, model-agnostic techniques trade off data locality for lower partitioning costs and balanced workloads which is beneficial when executing data-parallel single-pass graph algorithms.<\/jats:p>","DOI":"10.14778\/3236187.3236208","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"1590-1603","source":"Crossref","is-referenced-by-count":82,"title":["Streaming graph partitioning"],"prefix":"10.14778","volume":"11","author":[{"given":"Zainab","family":"Abbas","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden"}]},{"given":"Vasiliki","family":"Kalavri","sequence":"additional","affiliation":[{"name":"Systems Group ETH Zurich, Zurich, Switzerland"}]},{"given":"Paris","family":"Carbone","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden"}]},{"given":"Vladimir","family":"Vlassov","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden"}]}],"member":"320","published-online":{"date-parts":[[2018,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Storm project. http:\/\/storm.apache.org\/.  Apache Storm project. http:\/\/storm.apache.org\/."},{"key":"e_1_2_1_2_1","unstructured":"Grouplens. https:\/\/grouplens.org\/datasets\/movielens\/.  Grouplens. https:\/\/grouplens.org\/datasets\/movielens\/."},{"key":"e_1_2_1_3_1","unstructured":"Online social networks research at the Max Planck Institute for Software Systems. http:\/\/socialnetworks.mpi-sws.org\/data-imc2007.html.  Online social networks research at the Max Planck Institute for Software Systems. http:\/\/socialnetworks.mpi-sws.org\/data-imc2007.html."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007931"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623660"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2012.10.007"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137777"},{"key":"e_1_2_1_9_1","volume-title":"Apache Flink: Stream and batch processing in a single engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 36(4)","author":"Carbone P.","year":"2015"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526806"},{"key":"e_1_2_1_11_1","first-page":"442","volume-title":"SDM","author":"Chakrabarti D.","year":"2004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1983.234958"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323293.1294281"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_18_1","volume-title":"Graph partitioning-a survey","author":"Elsner U.","year":"1997"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_2_1_21_1","first-page":"2","volume-title":"OSDI","volume":"12","author":"Gonzalez J. E.","year":"2012"},{"key":"e_1_2_1_22_1","first-page":"599","volume-title":"11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14)","author":"Gonzalez J. E.","year":"2014"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/07069328X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2016.02.003"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00048-X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"e_1_2_1_27_1","first-page":"309","volume-title":"12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15)","author":"Iyer A.","year":"2015"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960419"},{"key":"e_1_2_1_29_1","volume-title":"Streaming graph analytics framework design","author":"Bali P. C. J. D.","year":"2015"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484429"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/3225632.3225755"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001576.2001642"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670997"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_35_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_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"1271","DOI":"10.1007\/978-0-387-39940-9_184","volume-title":"Encyclopedia of Database Systems","author":"McGregor A.","year":"2009"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-5412-3_12"},{"key":"e_1_2_1_43_1","first-page":"41","volume-title":"Presented as part of the 2012 USENIX Annual Technical Conference (USENIX ATC 12)","author":"Prabhakaran V.","year":"2012"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634169"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_46_1","volume-title":"Semi-streaming algorithms for annotated graph streams. arXiv preprint arXiv:1407.3462","author":"Thaler J.","year":"2014"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2817946.2817950"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055543"},{"key":"e_1_2_1_50_1","first-page":"1673","volume-title":"Advances in Neural Information Processing Systems","author":"Xie C.","year":"2014"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.138"},{"key":"e_1_2_1_52_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"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3236187.3236208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:46:53Z","timestamp":1672220813000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3236187.3236208"}},"subtitle":["an experimental study"],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":52,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["10.14778\/3236187.3236208"],"URL":"https:\/\/doi.org\/10.14778\/3236187.3236208","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}