{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:45:49Z","timestamp":1776969949250,"version":"3.51.4"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2026,4,23]]},"abstract":"<jats:p>Many graph workloads repeatedly run the same traversal or iterative computation from many different source vertices. Multi-instance execution can share work across sources and, if implemented carefully, exploit SIMD by packing per-source state into vectors. However, in vertex-centric graph processing systems, naive ''vectorize everything'' transformations can be wrong: a vertex may be active for only a subset of sources in a round, yet unguarded SIMD updates implicitly advance all lanes, leading to incorrect answers.<\/jats:p>\n                  <jats:p>We present AutoMI, a source-to-source compilation framework that automatically converts a single-instance program into a provably correct SIMD-vectorized multi-instance program runnable on existing vertex-centric engines. AutoMI uses a per-message bit-vector track to recover per-source activation and generate masked SIMD updates. It further provides a TrackFree optimization, guided by an algebraic idempotence characterization, that safely drops track and produces streamlined code when over-activation is harmless.<\/jats:p>\n                  <jats:p>On six real graphs (up to billions of edges) and up to 256 sources, AutoMI achieves 9.6 to 29.5x speedup over parallelized serial evaluation, 7.1 to 26.4x over batch processing, and 2.6 to 4.6x over prior handcrafted multi-instance code.<\/jats:p>","DOI":"10.1145\/3810900.3810904","type":"journal-article","created":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:16:38Z","timestamp":1776968198000},"page":"20-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["One Graph, Many Sources: Automating Vectorization Safely"],"prefix":"10.1145","volume":"55","author":[{"given":"Wenyue","family":"Zhao","sequence":"first","affiliation":[{"name":"The University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Cao","sequence":"additional","affiliation":[{"name":"The University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Buneman","sequence":"additional","affiliation":[{"name":"The University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Access","year":"2024","unstructured":"Friendster. http:\/\/konect.cc\/networks\/friendster\/, Access: 2024."},{"key":"e_1_2_1_2_1","volume-title":"Access","year":"2024","unstructured":"Giraph. https:\/\/giraph.apache.org\/, Access: 2024."},{"key":"e_1_2_1_3_1","volume-title":"Access","year":"2024","unstructured":"Intel\u00ae intrinsics guide. https:\/\/www.intel.com\/content\/www\/us\/en\/docs\/ intrinsics-guide\/index.html, Access: 2024."},{"key":"e_1_2_1_4_1","volume-title":"Access","year":"2024","unstructured":"libclang. https:\/\/clang.llvm.org\/, Access: 2024."},{"key":"e_1_2_1_5_1","volume-title":"Access","year":"2024","unstructured":"LiveJournal. http: \/\/snap.stanford.edu\/data\/soc-LiveJournal1.html, Access: 2024."},{"key":"e_1_2_1_6_1","volume-title":"Access","year":"2024","unstructured":"MovieLens. http:\/\/grouplens.org\/datasets\/movielens\/, Access: 2024."},{"key":"e_1_2_1_7_1","volume-title":"Access","year":"2024","unstructured":"Netflix. http:\/\/konect.cc\/networks\/netflix\/, Access: 2024."},{"key":"e_1_2_1_8_1","volume-title":"Access","year":"2024","unstructured":"Twitter. http:\/\/konect.cc\/networks\/twitter\/, Access: 2024."},{"key":"e_1_2_1_9_1","volume-title":"Access","author":"UK","year":"2024","unstructured":"UK domain. http:\/\/konect.cc\/networks\/dimacs10-uk-2007-05\/, Access: 2024."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.205"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231764"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 19th International Conference on Data Engineering","author":"Bruno N.","year":"2003","unstructured":"N. Bruno, L. Gravano, N. Koudas, and D. Srivastava. Navigation- vs. index-based XML multi-query processing. In U. Dayal, K. Ramamritham, and T. M. Vijayaraman, editors, Proceedings of the 19th International Conference on Data Engineering, March 5-8, 2003, Bangalore, India, pages 139-150. IEEE Computer Society, 2003."},{"key":"e_1_2_1_13_1","volume-title":"PowerLyra: Differentiated graph computation and partitioning on skewed graphs. ACM Transactions on Parallel Computing (TOPC), 5(3):1-39","author":"Chen R.","year":"2019","unstructured":"R. Chen, J. Shi, Y. Chen, B. Zang, H. Guan, and H. Chen. PowerLyra: Differentiated graph computation and partitioning on skewed graphs. ACM Transactions on Parallel Computing (TOPC), 5(3):1-39, 2019."},{"key":"e_1_2_1_14_1","first-page":"1","volume-title":"ICPP 2021:  50th International Conference on Parallel Processing","author":"Esfahani M. K.","year":"2021","unstructured":"M. K. Esfahani, P. Kilpatrick, and H. Vandierendonck. Exploiting in-hub temporal locality in spmv-based graph processing. In X. Sun, S. Shende, L. V. Kal\u00b4e, and Y. Chen, editors, ICPP 2021: 50th International Conference on Parallel Processing, Lemont, IL, USA, August 9 - 12, 2021, pages 42:1-42:10. ACM, 2021."},{"key":"e_1_2_1_15_1","first-page":"17","volume-title":"10th USENIX symposium on operating systems design and implementation (OSDI 12)","author":"Gonzalez J. E.","year":"2012","unstructured":"J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. PowerGraph: Distributed graph-parallel computation on natural graphs. In 10th USENIX symposium on operating systems design and implementation (OSDI 12), pages 17-30, 2012."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732980"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0305-0"},{"key":"e_1_2_1_18_1","first-page":"1","volume-title":"Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017","author":"Kaufmann M.","year":"2017","unstructured":"M. Kaufmann, M. Then, A. Kemper, and T. Neumann. Parallel array-based single- and multi-source breadth first searches on large dense graphs. In V. Markl, S. Orlando, B. Mitschang, P. Andritsos, K. Sattler, and S. Bre\u00df, editors, Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21-24, 2017, pages 1-12. OpenProceedings.org, 2017."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.263"},{"key":"e_1_2_1_20_1","first-page":"31","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012","author":"Kyrola A.","year":"2012","unstructured":"A. Kyrola, G. E. Blelloch, and C. Guestrin. GraphChi: Large-scale graph computation on just a PC. In C. Thekkath and A. Vahdat, editors, 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012, pages 31-46. USENIX Association, 2012."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.37"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the VLDB Endowment, 16(10)","author":"Li J.","year":"2023","unstructured":"J. Li, W. Zhao, N. Ntarmos, Y. Cao, and P. Buneman. MITra: A framework for multi-instance graph traversal. Proceedings of the VLDB Endowment, 16(10), 2023."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the VLDB Endowment, 5(8)","author":"Low Y.","year":"2012","unstructured":"Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. Distributed graphlab: A framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 5(8), 2012."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735517"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1109\/BigData47090.2019.9006359","volume-title":"2019 IEEE International Conference on Big Data (Big Data)","author":"Mazloumi A.","year":"2019","unstructured":"A. Mazloumi, X. Jiang, and R. Gupta. MultiLyra: Scalable distributed evaluation of batches of iterative graph queries. In 2019 IEEE International Conference on Big Data (Big Data), pages 349-358. IEEE, 2019."},{"key":"e_1_2_1_27_1","volume-title":"Thinking like a vertex: A survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Computing Surveys (CSUR), 48(2)","author":"McCune R. R.","year":"2015","unstructured":"R. R. McCune, T. Weninger, and G. Madey. Thinking like a vertex: A survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Computing Surveys (CSUR), 48(2), 2015."},{"key":"e_1_2_1_28_1","volume-title":"Stanford InfoLab","author":"Page L.","year":"1999","unstructured":"L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2947050"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021929"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/42201.42203"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.54724"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2017.27"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735507"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000056"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904488"},{"key":"e_1_2_1_38_1","first-page":"1","volume-title":"24th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2010, Atlanta, Georgia, USA, 19-23 April 2010 - Conference Proceedings","author":"Yanagisawa H.","year":"2010","unstructured":"H. Yanagisawa. A multi-source label-correcting algorithm for the all-pairs shortest paths problem. In 24th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2010, Atlanta, Georgia, USA, 19-23 April 2010 - Conference Proceedings, pages 1-10, 2010."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3127479.3128606"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"2189","DOI":"10.1145\/2882903.2899398","volume-title":"Proceedings of the 2016 International Conference on Management of Data, SIGMOD '16","author":"Zhang Q.","year":"2016","unstructured":"Q. Zhang, D. Yan, and J. Cheng. Quegel: A general-purpose system for querying big graphs. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD '16, pages 2189-2192. ACM, 2016."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698833"},{"key":"e_1_2_1_42_1","first-page":"4576","volume-title":"ICDE","author":"Zhao W.","year":"2025","unstructured":"W. Zhao, J. Li, Y. Cao, and N. Ntarmos. Mitra: Populating graph traversal algorithms. In ICDE, pages 4576-4579. IEEE, 2025."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3810900.3810904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:16:47Z","timestamp":1776968207000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3810900.3810904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,23]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,23]]}},"alternative-id":["10.1145\/3810900.3810904"],"URL":"https:\/\/doi.org\/10.1145\/3810900.3810904","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2026,4,23]]},"assertion":[{"value":"2026-04-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}