{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T09:35:31Z","timestamp":1774949731698,"version":"3.50.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:p>This paper presents MITra, a framework for composing multi-instance graph algorithms that traverse from multiple source vertices simultaneously over a single thread. Underlying MITra is a model of multi-instance traversal that uniformly captures traversal sharing across instances. Based on this, MITra provides a programming model that allows users to express traversals by declaring vertex ranks and specify computation logic via an edge function. It synthesizes multi-instance traversal algorithms from declared vertex ranks and edge functions adopted from classic single-instance algorithms, automatically sharing computation across instances and benefiting from SIMD. We show that MITra can generate multi-instance algorithms provably better than existing ones, while being more expressive than traditional frameworks. In addition to the ease of programming, we experimentally verify that MITra is on average an order of magnitude faster than approaches based on existing frameworks for common graph algorithms, and is comparable to the state-of-the-art highly optimized one-off algorithms.<\/jats:p>","DOI":"10.14778\/3603581.3603594","type":"journal-article","created":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T19:06:48Z","timestamp":1691521608000},"page":"2551-2564","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["MITra: A Framework for Multi-Instance Graph Traversal"],"prefix":"10.14778","volume":"16","author":[{"given":"Jia","family":"Li","sequence":"first","affiliation":[{"name":"Edinburgh Research Centre, Huawei"}]},{"given":"Wenyue","family":"Zhao","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}]},{"given":"Nikos","family":"Ntarmos","sequence":"additional","affiliation":[{"name":"Edinburgh Research Centre, Huawei"}]},{"given":"Yang","family":"Cao","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}]},{"given":"Peter","family":"Buneman","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}]}],"member":"320","published-online":{"date-parts":[[2023,8,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Giraph. https:\/\/giraph.apache.org\/.  Giraph. https:\/\/giraph.apache.org\/."},{"key":"e_1_2_1_2_1","unstructured":"Intel\u00ae intrinsics guide. https:\/\/www.intel.com\/content\/www\/us\/en\/docs\/intrinsics-guide\/index.html.  Intel\u00ae intrinsics guide. https:\/\/www.intel.com\/content\/www\/us\/en\/docs\/intrinsics-guide\/index.html."},{"key":"e_1_2_1_3_1","unstructured":"LiveJournal. http:\/\/snap.stanford.edu\/data\/soc-LiveJournal1.html.  LiveJournal. http:\/\/snap.stanford.edu\/data\/soc-LiveJournal1.html."},{"key":"e_1_2_1_4_1","unstructured":"Pokec. http:\/\/snap.stanford.edu\/data\/soc-Pokec.html.  Pokec. http:\/\/snap.stanford.edu\/data\/soc-Pokec.html."},{"key":"e_1_2_1_5_1","unstructured":"Snap Library. https:\/\/snap.stanford.edu\/snap\/description.html.  Snap Library. https:\/\/snap.stanford.edu\/snap\/description.html."},{"key":"e_1_2_1_6_1","unstructured":"The source code for Ligra framework. https:\/\/github.com\/jshun\/ligra.  The source code for Ligra framework. https:\/\/github.com\/jshun\/ligra."},{"key":"e_1_2_1_7_1","unstructured":"The source code for MS-BFS algorithm. https:\/\/github.com\/mtodat\/ms-bfs.  The source code for MS-BFS algorithm. https:\/\/github.com\/mtodat\/ms-bfs."},{"key":"e_1_2_1_8_1","unstructured":"Twitter. http:\/\/konect.cc\/networks\/twitter\/.  Twitter. http:\/\/konect.cc\/networks\/twitter\/."},{"key":"e_1_2_1_9_1","unstructured":"UK domain. http:\/\/konect.cc\/networks\/dimacs10-uk-2007-05\/.  UK domain. http:\/\/konect.cc\/networks\/dimacs10-uk-2007-05\/."},{"key":"e_1_2_1_10_1","unstructured":"UK\/DE\/EU Traffic. https:\/\/www.cc.gatech.edu\/dimacs10\/archive\/streets.shtml.  UK\/DE\/EU Traffic. https:\/\/www.cc.gatech.edu\/dimacs10\/archive\/streets.shtml."},{"key":"e_1_2_1_11_1","unstructured":"US Traffic. http:\/\/www.diag.uniroma1.it\/\/challenge9\/download.shtml.  US Traffic. http:\/\/www.diag.uniroma1.it\/\/challenge9\/download.shtml."},{"key":"e_1_2_1_12_1","first-page":"1426","volume-title":"33rd IEEE International Conference on Data Engineering, ICDE 2017","author":"Abul-Basher Z.","year":"2017","unstructured":"Z. Abul-Basher . Multiple-query optimization of regular path queries . In 33rd IEEE International Conference on Data Engineering, ICDE 2017 , San Diego, CA, USA, April 19--22 , 2017 , pages 1426 -- 1430 . IEEE Computer Society, 2017. Z. Abul-Basher. Multiple-query optimization of regular path queries. In 33rd IEEE International Conference on Data Engineering, ICDE 2017, San Diego, CA, USA, April 19--22, 2017, pages 1426--1430. IEEE Computer Society, 2017."},{"key":"e_1_2_1_13_1","volume-title":"SIGMOD. ACM","author":"Akiba T.","year":"2013","unstructured":"T. Akiba , Y. Iwata , and Y. Yoshida . Fast exact shortest-path distance queries on large networks by pruned landmark labeling . In SIGMOD. ACM , 2013 . T. Akiba, Y. Iwata, and Y. Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD. ACM, 2013."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 19th International Conference on Data Engineering, March 5--8, 2003","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 . 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_15_1","first-page":"442","volume-title":"Proceedings of the 2004 SIAM International Conference on Data Mining","author":"Chakrabarti D.","year":"2004","unstructured":"D. Chakrabarti , Y. Zhan , and C. Faloutsos . R-MAT: A recursive model for graph mining . In Proceedings of the 2004 SIAM International Conference on Data Mining , pages 442 -- 446 . SIAM, 2004 . D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-MAT: A recursive model for graph mining. In Proceedings of the 2004 SIAM International Conference on Data Mining, pages 442--446. SIAM, 2004."},{"key":"e_1_2_1_16_1","volume-title":"Introduction to algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to algorithms . MIT press , 2009 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT press, 2009."},{"key":"e_1_2_1_17_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\u00e9, 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. 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\u00e9, 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_18_1","volume-title":"Mathematical structures for computer science (3. ed.)","author":"Gersting J. L.","year":"1993","unstructured":"J. L. Gersting . Mathematical structures for computer science (3. ed.) . Computer Science Press , 1993 . J. L. Gersting. Mathematical structures for computer science (3. ed.). Computer Science Press, 1993."},{"key":"e_1_2_1_19_1","first-page":"17","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012","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 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 17 -- 30 . USENIX Association, 2012. J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. PowerGraph: Distributed graph-parallel computation on natural graphs. 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 17--30. USENIX Association, 2012."},{"key":"e_1_2_1_20_1","first-page":"77","volume-title":"The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013","author":"Han W.","year":"2013","unstructured":"W. Han , S. Lee , K. Park , J. Lee , M. Kim , J. Kim , and H. Yu . TurboGraph: a fast parallel graph engine handling billion-scale graphs in a single PC . In The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013 , Chicago, IL, USA, August 11--14 , 2013 , pages 77 -- 85 . ACM, 2013. W. Han, S. Lee, K. Park, J. Lee, M. Kim, J. Kim, and H. Yu. TurboGraph: a fast parallel graph engine handling billion-scale graphs in a single PC. In The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, IL, USA, August 11--14, 2013, pages 77--85. ACM, 2013."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1145\/775152.775191","volume-title":"Proceedings of the Twelfth International World Wide Web Conference, WWW 2003","author":"Jeh G.","year":"2003","unstructured":"G. Jeh and J. Widom . Scaling personalized web search. In G. Hencsey, B. White, Y. R. Chen, L. Kov\u00e1cs, and S. Lawrence, editors , Proceedings of the Twelfth International World Wide Web Conference, WWW 2003 , Budapest, Hungary, May 20--24 , 2003 , pages 271 -- 279 . ACM, 2003. G. Jeh and J. Widom. Scaling personalized web search. In G. Hencsey, B. White, Y. R. Chen, L. Kov\u00e1cs, and S. Lawrence, editors, Proceedings of the Twelfth International World Wide Web Conference, WWW 2003, Budapest, Hungary, May 20--24, 2003, pages 271--279. ACM, 2003."},{"key":"e_1_2_1_22_1","unstructured":"U. Kang D. H. Chau and C. Faloutsos. Mining large graphs: Algorithms inference and discoveries. In ICDE.  U. Kang D. H. Chau and C. Faloutsos. Mining large graphs: Algorithms inference and discoveries. In ICDE."},{"issue":"2","key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10115-010-0305-0","article-title":"PEGASUS: mining peta-scale graphs","volume":"27","author":"Kang U.","year":"2011","unstructured":"U. Kang , C. E. Tsourakakis , and C. Faloutsos . PEGASUS: mining peta-scale graphs . Knowl. Inf. Syst. , 27 ( 2 ): 303 -- 325 , 2011 . U. Kang, C. E. Tsourakakis, and C. Faloutsos. PEGASUS: mining peta-scale graphs. Knowl. Inf. Syst., 27(2):303--325, 2011.","journal-title":"Knowl. Inf. Syst."},{"key":"e_1_2_1_24_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. 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."},{"issue":"5","key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/324133.324140","article-title":"Authoritative sources in a hyperlinked environment","volume":"46","author":"Kleinberg J. M.","year":"1999","unstructured":"J. M. Kleinberg . Authoritative sources in a hyperlinked environment . J. ACM , 46 ( 5 ): 604 -- 632 , 1999 . J. M. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46(5):604--632, 1999.","journal-title":"J. ACM"},{"key":"e_1_2_1_26_1","first-page":"177","volume-title":"Regular path queries on large graphs","author":"Koschmieder A.","year":"2012","unstructured":"A. Koschmieder and U. Leser . Regular path queries on large graphs . In A. Ailamaki and S. Bowers, editors, SSDBM, volume 7338 , pages 177 -- 194 . Springer , 2012 . A. Koschmieder and U. Leser. Regular path queries on large graphs. In A. Ailamaki and S. Bowers, editors, SSDBM, volume 7338, pages 177--194. Springer, 2012."},{"key":"e_1_2_1_27_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. 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_28_1","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1109\/ICDE.2012.37","volume-title":"IEEE 28th International Conference on Data Engineering (ICDE 2012","author":"Le W.","year":"2012","unstructured":"W. Le , A. Kementsietsidis , S. Duan , and F. Li . Scalable multi-query optimization for SPARQL. In A. Kementsietsidis and M. A. V. Salles, editors , IEEE 28th International Conference on Data Engineering (ICDE 2012 ), Washington, DC, USA (Arlington, Virginia), 1- -5 April , 2012 , pages 666 -- 677 . IEEE Computer Society, 2012. W. Le, A. Kementsietsidis, S. Duan, and F. Li. Scalable multi-query optimization for SPARQL. In A. Kementsietsidis and M. A. V. Salles, editors, IEEE 28th International Conference on Data Engineering (ICDE 2012), Washington, DC, USA (Arlington, Virginia), 1--5 April, 2012, pages 666--677. IEEE Computer Society, 2012."},{"key":"e_1_2_1_29_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1007\/978-3-030-87571-8_55","volume-title":"C. Xing","author":"Liu X.","year":"2021","unstructured":"X. Liu , Z. Wang , N. Wang , X. Li , B. Zhang , J. Qiao , Z. Wei , and J. Nie . An adaptive sharing framework for efficient multi-source shortest path computation . In C. Xing , X. Fu, Y. Zhang, G. Zhang, and C. Borjigin, editors, Web Information Systems and Applications - 18th International Conference, WISA 2021 , Kaifeng, China, September 24--26, 2021, Proceedings, volume 12999 of Lecture Notes in Computer Science , pages 635 -- 646 . Springer , 2021. X. Liu, Z. Wang, N. Wang, X. Li, B. Zhang, J. Qiao, Z. Wei, and J. Nie. An adaptive sharing framework for efficient multi-source shortest path computation. In C. Xing, X. Fu, Y. Zhang, G. Zhang, and C. Borjigin, editors, Web Information Systems and Applications - 18th International Conference, WISA 2021, Kaifeng, China, September 24--26, 2021, Proceedings, volume 12999 of Lecture Notes in Computer Science, pages 635--646. Springer, 2021."},{"issue":"8","key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"716","DOI":"10.14778\/2212351.2212354","article-title":"Distributed GraphLab: A framework for machine learning in the cloud","volume":"5","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 in the cloud . Proc. VLDB Endow. , 5 ( 8 ): 716 -- 727 , 2012 . Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. Distributed GraphLab: A framework for machine learning in the cloud. Proc. VLDB Endow., 5(8):716--727, 2012.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_31_1","first-page":"1208","volume-title":"SIGMOD '21: International Conference on Management of Data","author":"Lu S.","year":"2021","unstructured":"S. Lu , S. Sun , J. Paul , Y. Li , and B. He . Cache-efficient fork-processing patterns on large graphs. In G. Li, Z. Li, S. Idreos, and D. Srivastava, editors , SIGMOD '21: International Conference on Management of Data , Virtual Event, China, June 20--25 , 2021 , pages 1208 -- 1221 . ACM, 2021. S. Lu, S. Sun, J. Paul, Y. Li, and B. He. Cache-efficient fork-processing patterns on large graphs. In G. Li, Z. Li, S. Idreos, and D. Srivastava, editors, SIGMOD '21: International Conference on Management of Data, Virtual Event, China, June 20--25, 2021, pages 1208--1221. ACM, 2021."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/1807167.1807184","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010","author":"Malewicz G.","year":"2010","unstructured":"G. Malewicz , M. H. Austern , A. J. C. Bik , J. C. Dehnert , I. Horn , N. Leiser , and G. Czajkowski . Pregel: a system for large-scale graph processing. In A. K. Elmagarmid and D. Agrawal, editors , Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010 , Indianapolis, Indiana, USA, June 6--10 , 2010 , pages 135 -- 146 . ACM, 2010. G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In A. K. Elmagarmid and D. Agrawal, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June 6--10, 2010, pages 135--146. ACM, 2010."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1109\/BigData47090.2019.9006359","volume-title":"2019 IEEE International Conference on Big Data (IEEE BigData)","author":"Mazloumi A.","year":"2019","unstructured":"A. Mazloumi , X. Jiang , and R. Gupta . MultiLyra: Scalable distributed evaluation of batches of iterative graph queries. In C. Baru, J. Huan, L. Khan, X. Hu, R. Ak, Y. Tian, R. S. Barga, C. Zaniolo, K. Lee, and Y. F. Ye, editors , 2019 IEEE International Conference on Big Data (IEEE BigData) , Los Angeles, CA, USA, December 9--12 , 2019 , pages 349 -- 358 . IEEE, 2019. A. Mazloumi, X. Jiang, and R. Gupta. MultiLyra: Scalable distributed evaluation of batches of iterative graph queries. In C. Baru, J. Huan, L. Khan, X. Hu, R. Ak, Y. Tian, R. S. Barga, C. Zaniolo, K. Lee, and Y. F. Ye, editors, 2019 IEEE International Conference on Big Data (IEEE BigData), Los Angeles, CA, USA, December 9--12, 2019, pages 349--358. IEEE, 2019."},{"issue":"1","key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/S0196-6774(03)00076-2","article-title":"Delta-stepping: a parallelizable shortest path algorithm","volume":"49","author":"Meyer U.","year":"2003","unstructured":"U. Meyer and P. Sanders . Delta-stepping: a parallelizable shortest path algorithm . J. Algorithms , 49 ( 1 ): 114 -- 152 , 2003 . U. Meyer and P. Sanders. Delta-stepping: a parallelizable shortest path algorithm. J. Algorithms, 49(1):114--152, 2003.","journal-title":"J. Algorithms"},{"key":"e_1_2_1_35_1","first-page":"456","volume-title":"ACM SIGOPS 24th Symposium on Operating Systems Principles, SOSP'13","author":"Nguyen D.","year":"2013","unstructured":"D. Nguyen , A. Lenharth , and K. Pingali . A lightweight infrastructure for graph analytics. In M. Kaminsky and M. Dahlin, editors , ACM SIGOPS 24th Symposium on Operating Systems Principles, SOSP'13 , Farmington, PA, USA, November 3--6 , 2013 , pages 456 -- 471 . ACM, 2013. D. Nguyen, A. Lenharth, and K. Pingali. A lightweight infrastructure for graph analytics. In M. Kaminsky and M. Dahlin, editors, ACM SIGOPS 24th Symposium on Operating Systems Principles, SOSP'13, Farmington, PA, USA, November 3--6, 2013, pages 456--471. ACM, 2013."},{"key":"e_1_2_1_36_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 . 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_37_1","first-page":"217","volume-title":"2017 IEEE International Conference on Computer Design, ICCD 2017","author":"Pan P.","year":"2017","unstructured":"P. Pan and C. Li . Congra: Towards efficient processing of concurrent graph queries on shared-memory machines . In 2017 IEEE International Conference on Computer Design, ICCD 2017 , Boston, MA, USA, November 5--8 , 2017 , pages 217 -- 224 . IEEE Computer Society, 2017. P. Pan and C. Li. Congra: Towards efficient processing of concurrent graph queries on shared-memory machines. In 2017 IEEE International Conference on Computer Design, ICCD 2017, Boston, MA, USA, November 5--8, 2017, pages 217--224. IEEE Computer Society, 2017."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1145\/3394885.3431548","volume-title":"ASPDAC","author":"Parravicini A.","year":"2021","unstructured":"A. Parravicini , F. Sgherzi , and M. D. Santambrogio . A reduced-precision streaming spmv architecture for personalized pagerank on FPGA . In ASPDAC , pages 378 -- 383 . ACM, 2021 . A. Parravicini, F. Sgherzi, and M. D. Santambrogio. A reduced-precision streaming spmv architecture for personalized pagerank on FPGA. In ASPDAC, pages 378--383. ACM, 2021."},{"issue":"4","key":"e_1_2_1_39_1","doi-asserted-by":"crossref","first-page":"1692","DOI":"10.1109\/TKDE.2019.2947050","article-title":"Optimizing multi-query evaluation in federated RDF systems","volume":"33","author":"Peng P.","year":"2021","unstructured":"P. Peng , Q. Ge , L. Zou , M. T. \u00d6zsu , Z. Xu , and D. Zhao . Optimizing multi-query evaluation in federated RDF systems . IEEE Trans. Knowl. Data Eng. , 33 ( 4 ): 1692 -- 1707 , 2021 . P. Peng, Q. Ge, L. Zou, M. T. \u00d6zsu, Z. Xu, and D. Zhao. Optimizing multi-query evaluation in federated RDF systems. IEEE Trans. Knowl. Data Eng., 33(4):1692--1707, 2021.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/978-3-030-99372-6_7","volume-title":"International Workshop on Languages and Compilers for Parallel Computing","author":"Qiu S.","year":"2022","unstructured":"S. Qiu , L. You , and Z. Wang . Optimizing sparse matrix multiplications for graph neural networks . In International Workshop on Languages and Compilers for Parallel Computing , pages 101 -- 117 . Springer , 2022 . S. Qiu, L. You, and Z. Wang. Optimizing sparse matrix multiplications for graph neural networks. In International Workshop on Languages and Compilers for Parallel Computing, pages 101--117. Springer, 2022."},{"issue":"3","key":"e_1_2_1_41_1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.14778\/3021924.3021929","article-title":"Multi-query optimization for subgraph isomorphism search","volume":"10","author":"Ren X.","year":"2016","unstructured":"X. Ren and J. Wang . Multi-query optimization for subgraph isomorphism search . Proc. VLDB Endow. , 10 ( 3 ): 121 -- 132 , 2016 . X. Ren and J. Wang. Multi-query optimization for subgraph isomorphism search. Proc. VLDB Endow., 10(3):121--132, 2016.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1145\/2517349.2522740","volume-title":"Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles","author":"Roy A.","year":"2013","unstructured":"A. Roy , I. Mihailovic , and W. Zwaenepoel . X-stream: Edge-centric graph processing using streaming partitions . In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles , pages 472 -- 488 , 2013 . A. Roy, I. Mihailovic, and W. Zwaenepoel. X-stream: Edge-centric graph processing using streaming partitions. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 472--488, 2013."},{"issue":"1","key":"e_1_2_1_43_1","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/42201.42203","article-title":"Multiple-query optimization","volume":"13","author":"Sellis T. K.","year":"1988","unstructured":"T. K. Sellis . Multiple-query optimization . ACM Trans. Database Syst. , 13 ( 1 ): 23 -- 52 , 1988 . T. K. Sellis. Multiple-query optimization. ACM Trans. Database Syst., 13(1):23--52, 1988.","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"e_1_2_1_44_1","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1109\/69.54724","article-title":"On the multiple-query optimization problem","volume":"2","author":"Sellis T. K.","year":"1990","unstructured":"T. K. Sellis and S. Ghosh . On the multiple-query optimization problem . IEEE Trans. Knowl. Data Eng. , 2 ( 2 ): 262 -- 266 , 1990 . T. K. Sellis and S. Ghosh. On the multiple-query optimization problem. IEEE Trans. Knowl. Data Eng., 2(2):262--266, 1990.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_45_1","volume-title":"ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '13","author":"Shun J.","year":"2013","unstructured":"J. Shun and G. E. Blelloch . Ligra: a lightweight graph processing framework for shared memory. In A. Nicolau, X. Shen, S. P. Amarasinghe, and R. W. Vuduc, editors , ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '13 , Shenzhen, China, February 23--27 , 2013 . J. Shun and G. E. Blelloch. Ligra: a lightweight graph processing framework for shared memory. In A. Nicolau, X. Shen, S. P. Amarasinghe, and R. W. Vuduc, editors, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '13, Shenzhen, China, February 23--27, 2013."},{"key":"e_1_2_1_46_1","volume-title":"S. Skiena. The Algorithm Design Manual","year":"2008","unstructured":"S. Skiena. The Algorithm Design Manual , Second Edition. Springer , 2008 . S. Skiena. The Algorithm Design Manual, Second Edition. Springer, 2008."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1109\/ICPP.2017.27","volume-title":"2017 46th International Conference on Parallel Processing (ICPP)","author":"Sun J.","year":"2017","unstructured":"J. Sun , H. Vandierendonck , and D. S. Nikolopoulos . Accelerating graph analytics by utilising the memory locality of graph partitioning . In 2017 46th International Conference on Parallel Processing (ICPP) , pages 181 -- 190 . IEEE, 2017 . J. Sun, H. Vandierendonck, and D. S. Nikolopoulos. Accelerating graph analytics by utilising the memory locality of graph partitioning. In 2017 46th International Conference on Parallel Processing (ICPP), pages 181--190. IEEE, 2017."},{"issue":"4","key":"e_1_2_1_48_1","doi-asserted-by":"crossref","first-page":"449","DOI":"10.14778\/2735496.2735507","article-title":"The more the merrier: Efficient multi-source graph traversal","volume":"8","author":"Then M.","year":"2014","unstructured":"M. Then , M. Kaufmann , F. Chirigati , T. Hoang-Vu , K. Pham , A. Kemper , T. Neumann , and H. T. Vo . The more the merrier: Efficient multi-source graph traversal . Proc. VLDB Endow. , 8 ( 4 ): 449 -- 460 , 2014 . M. Then, M. Kaufmann, F. Chirigati, T. Hoang-Vu, K. Pham, A. Kemper, T. Neumann, and H. T. Vo. The more the merrier: Efficient multi-source graph traversal. Proc. VLDB Endow., 8(4):449--460, 2014.","journal-title":"Proc. VLDB Endow."},{"issue":"3","key":"e_1_2_1_49_1","doi-asserted-by":"crossref","first-page":"193","DOI":"10.14778\/2732232.2732238","article-title":"From \"think like a vertex\" to \"think like a graph","volume":"7","author":"Tian Y.","year":"2013","unstructured":"Y. Tian , A. Balmin , S. A. Corsten , S. Tatikonda , and J. McPherson . From \"think like a vertex\" to \"think like a graph \". Proc. VLDB Endow. , 7 ( 3 ): 193 -- 204 , 2013 . Y. Tian, A. Balmin, S. A. Corsten, S. Tatikonda, and J. McPherson. From \"think like a vertex\" to \"think like a graph\". Proc. VLDB Endow., 7(3):193--204, 2013.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_50_1","first-page":"943","volume-title":"J","author":"Valiant L. G.","year":"1990","unstructured":"L. G. Valiant . General purpose parallel architectures. In J . van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A : Algorithms and Complexity, pages 943 -- 972 . Elsevier and MIT Press , 1990 . L. G. Valiant. General purpose parallel architectures. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pages 943--972. Elsevier and MIT Press, 1990."},{"key":"e_1_2_1_51_1","first-page":"505","volume-title":"Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13 - 17, 2017","author":"Wang S.","year":"2017","unstructured":"S. Wang , R. Yang , X. Xiao , Z. Wei , and Y. Yang . FORA: simple and effective approximate single-source personalized pagerank . In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13 - 17, 2017 , pages 505 -- 514 . ACM, 2017 . S. Wang, R. Yang, X. Xiao, Z. Wei, and Y. Yang. FORA: simple and effective approximate single-source personalized pagerank. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13 - 17, 2017, pages 505--514. ACM, 2017."},{"key":"e_1_2_1_52_1","first-page":"441","volume-title":"Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018","author":"Wei Z.","year":"2018","unstructured":"Z. Wei , X. He , X. Xiao , S. Wang , S. Shang , and J. Wen . TopPPR: Top-k personalized pagerank queries with precision guarantees on large graphs. In G. Das, C. M. Jermaine, and P. A. Bernstein, editors , Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018 , Houston, TX, USA, June 10--15 , 2018 , pages 441 -- 456 . ACM, 2018. Z. Wei, X. He, X. Xiao, S. Wang, S. Shang, and J. Wen. TopPPR: Top-k personalized pagerank queries with precision guarantees on large graphs. In G. Das, C. M. Jermaine, and P. A. Bernstein, editors, Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10--15, 2018, pages 441--456. ACM, 2018."},{"key":"e_1_2_1_53_1","first-page":"1","volume-title":"27th IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2020","author":"Xu C.","year":"2020","unstructured":"C. Xu , A. Mazloumi , X. Jiang , and R. Gupta . SimGQ: Simultaneously evaluating iterative graph queries . In 27th IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2020 , Pune, India, December 16--19 , 2020 , pages 1 -- 10 . IEEE, 2020. C. Xu, A. Mazloumi, X. Jiang, and R. Gupta. SimGQ: Simultaneously evaluating iterative graph queries. In 27th IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2020, Pune, India, December 16--19, 2020, pages 1--10. IEEE, 2020."},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.jpdc.2022.01.007","article-title":"SimGQ+: Simultaneously evaluating iterative point-to-all and point-to-point graph queries","volume":"164","author":"Xu C.","year":"2022","unstructured":"C. Xu , A. Mazloumi , X. Jiang , and R. Gupta . SimGQ+: Simultaneously evaluating iterative point-to-all and point-to-point graph queries . Journal of Parallel and Distributed Computing , 164 : 12 -- 27 , 2022 . C. Xu, A. Mazloumi, X. Jiang, and R. Gupta. SimGQ+: Simultaneously evaluating iterative point-to-all and point-to-point graph queries. Journal of Parallel and Distributed Computing, 164:12--27, 2022.","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"14","key":"e_1_2_1_55_1","doi-asserted-by":"crossref","first-page":"1981","DOI":"10.14778\/2733085.2733103","article-title":"A block-centric framework for distributed computation on real-world graphs","volume":"7","author":"Yan D.","year":"2014","unstructured":"D. Yan , J. Cheng , Y. Lu , and W. Ng. Blogel : A block-centric framework for distributed computation on real-world graphs . Proc. VLDB Endow. , 7 ( 14 ): 1981 -- 1992 , 2014 . D. Yan, J. Cheng, Y. Lu, and W. Ng. Blogel: A block-centric framework for distributed computation on real-world graphs. Proc. VLDB Endow., 7(14):1981--1992, 2014.","journal-title":"Proc. VLDB Endow."},{"issue":"7","key":"e_1_2_1_56_1","doi-asserted-by":"crossref","first-page":"564","DOI":"10.14778\/2904483.2904488","article-title":"A general-purpose query-centric framework for querying big graphs","volume":"9","author":"Yan D.","year":"2016","unstructured":"D. Yan , J. Cheng , M. T. \u00d6zsu , F. Yang , Y. Lu , J. C. S. Lui , Q. Zhang , and W. Ng . A general-purpose query-centric framework for querying big graphs . Proc. VLDB Endow. , 9 ( 7 ): 564 -- 575 , 2016 . D. Yan, J. Cheng, M. T. \u00d6zsu, F. Yang, Y. Lu, J. C. S. Lui, Q. Zhang, and W. Ng. A general-purpose query-centric framework for querying big graphs. Proc. VLDB Endow., 9(7):564--575, 2016.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_57_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 . 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_58_1","first-page":"441","volume-title":"CGraph: A correlations-aware approach for efficient concurrent iterative graph processing","author":"Zhang Y.","year":"2018","unstructured":"Y. Zhang , X. Liao , H. Jin , L. Gu , L. He , B. He , and H. Liu . CGraph: A correlations-aware approach for efficient concurrent iterative graph processing . In H. S. Gunawi and B. Reed, editors, 2018 USENIX Annual Technical Conference, USENIX ATC 2018, Boston, MA, USA, July 11--13, 2018, pages 441 -- 452 . USENIX Association , 2018. Y. Zhang, X. Liao, H. Jin, L. Gu, L. He, B. He, and H. Liu. CGraph: A correlations-aware approach for efficient concurrent iterative graph processing. In H. S. Gunawi and B. Reed, editors, 2018 USENIX Annual Technical Conference, USENIX ATC 2018, Boston, MA, USA, July 11--13, 2018, pages 441--452. USENIX Association, 2018."},{"key":"e_1_2_1_59_1","volume-title":"Proc. ACM Program. Lang., 2(OOPSLA):121:1--121:30","author":"Zhang Y.","year":"2018","unstructured":"Y. Zhang , M. Yang , R. Baghdadi , S. Kamil , J. Shun , and S. P. Amarasinghe . GraphIt: a high-performance graph DSL . Proc. ACM Program. Lang., 2(OOPSLA):121:1--121:30 , 2018 . Y. Zhang, M. Yang, R. Baghdadi, S. Kamil, J. Shun, and S. P. Amarasinghe. GraphIt: a high-performance graph DSL. Proc. ACM Program. Lang., 2(OOPSLA):121:1--121:30, 2018."},{"key":"e_1_2_1_60_1","first-page":"1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2019","author":"Zhao J.","year":"2019","unstructured":"J. Zhao , Y. Zhang , X. Liao , L. He , B. He , H. Jin , H. Liu , and Y. Chen . GraphM: an efficient storage system for high throughput of concurrent graph processing. In M. Taufer, P. Balaji, and A. J. Pe\u00f1a, editors , Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2019 , Denver, Colorado, USA, November 17--19 , 2019 , pages 3: 1 -- 3 :14. ACM, 2019. J. Zhao, Y. Zhang, X. Liao, L. He, B. He, H. Jin, H. Liu, and Y. Chen. GraphM: an efficient storage system for high throughput of concurrent graph processing. In M. Taufer, P. Balaji, and A. J. Pe\u00f1a, editors, Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2019, Denver, Colorado, USA, November 17--19, 2019, pages 3:1--3:14. ACM, 2019."},{"key":"e_1_2_1_61_1","first-page":"301","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016","author":"Zhu X.","year":"2016","unstructured":"X. Zhu , W. Chen , W. Zheng , and X. Ma . Gemini: A computation-centric distributed graph processing system. In K. Keeton and T. Roscoe, editors , 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016 , Savannah, GA, USA, November 2--4 , 2016 , pages 301 -- 316 . USENIX Association, 2016. X. Zhu, W. Chen, W. Zheng, and X. Ma. Gemini: A computation-centric distributed graph processing system. In K. Keeton and T. Roscoe, editors, 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2--4, 2016, pages 301--316. USENIX Association, 2016."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3603581.3603594","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T19:10:31Z","timestamp":1691521831000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3603581.3603594"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":61,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["10.14778\/3603581.3603594"],"URL":"https:\/\/doi.org\/10.14778\/3603581.3603594","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"2023-08-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}