{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T07:54:11Z","timestamp":1782892451290,"version":"3.54.5"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T00:00:00Z","timestamp":1620604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            There has been a rise in the popularity of algebraic methods for graph algorithms given the development of the GraphBLAS library and other sparse matrix methods. An exemplar for these approaches is Breadth-First Search (BFS). The algebraic BFS algorithm is simply a recurrence of matrix-vector multiplications with the\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            adjacency matrix, but the many redundant operations over nonzeros ultimately lead to suboptimal performance. Therefore an optimal algebraic BFS should be of keen interest especially if it is easily integrated with existing matrix methods.\n          <\/jats:p>\n          <jats:p>Current methods, notably in the GraphBLAS, use a Sparse Matrix masked-Sparse Vector multiplication in which the input vector is kept in a sparse representation in each step of the BFS, and nonzeros in the vector are masked in subsequent steps. This has been an area of recent research in GraphBLAS and other libraries. While in theory, these masking methods are asymptotically optimal on sparse graphs, many add work that leads to suboptimal runtime. We give a new optimal, algebraic BFS for sparse graphs, thus closing a gap in the literature.<\/jats:p>\n          <jats:p>\n            Our method multiplies progressively smaller submatrices of the adjacency matrix at each step. Let\n            <jats:italic>n<\/jats:italic>\n            and\n            <jats:italic>m<\/jats:italic>\n            refer to the number of vertices and edges, respectively. On a sparse graph, our method takes\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) algebraic operations as opposed to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            ) operations needed by theoretically optimal sparse matrix approaches. Thus, for sparse graphs, it matches the bounds of the best-known sequential algorithm, and on a Parallel Random Access Machine, it is work-optimal. Our result holds for both directed and undirected graphs. Compared to a leading GraphBLAS library, our method achieves up to 24x faster sequential time, and for parallel computation, it can be 17x faster on large graphs and 12x faster on large-diameter graphs.\n          <\/jats:p>","DOI":"10.1145\/3446216","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T22:24:14Z","timestamp":1620685454000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Optimal Algebraic Breadth-First Search for Sparse Graphs"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5472-2963","authenticated-orcid":false,"given":"Paul","family":"Burkhardt","sequence":"first","affiliation":[{"name":"Research Directorate, National Security Agency"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,5,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.76"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389013"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.93"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 2014 International Conference on Mathematics and Computers in Sciences and in Industry. 33--35","author":"Martin B\u00fccker H.","year":"2014","unstructured":"H. Martin B\u00fccker and Christian Sohr . 2014 . Reformulating a breadth-first search algorithm on an undirected graph in the language of linear algebra . In Proceedings of the 2014 International Conference on Mathematics and Computers in Sciences and in Industry. 33--35 . H. Martin B\u00fccker and Christian Sohr. 2014. Reformulating a breadth-first search algorithm on an undirected graph in the language of linear algebra. In Proceedings of the 2014 International Conference on Mathematics and Computers in Sciences and in Industry. 33--35."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063471"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2017.117"},{"key":"e_1_2_1_8_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). The MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press.","edition":"3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2018.8547538"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322125"},{"key":"e_1_2_1_11_1","unstructured":"Timothy A. Davis. 2019. SuiteSparse:GraphBLAS. Retrieved from http:faculty.cse.tamu.edu\/davis\/GraphBLAS.html.  Timothy A. Davis. 2019. SuiteSparse:GraphBLAS. Retrieved from http:faculty.cse.tamu.edu\/davis\/GraphBLAS.html."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0613024"},{"key":"e_1_2_1_15_1","volume-title":"Intel Math Kernel Library. Reference Manual","unstructured":"Intel. 2009. Intel Math Kernel Library. Reference Manual . Intel Corporation , Santa Clara . Intel. 2009. Intel Math Kernel Library. Reference Manual. Intel Corporation, Santa Clara."},{"key":"e_1_2_1_16_1","volume-title":"An Introduction to Parallel Algorithms","author":"JaJa Joseph","unstructured":"Joseph JaJa . 1992. An Introduction to Parallel Algorithms . Addison Wesley . Joseph JaJa. 1992. An Introduction to Parallel Algorithms. Addison Wesley."},{"key":"e_1_2_1_17_1","volume-title":"Graph Algorithms in the Language of Linear Algebra","author":"Kepner Jeremy","unstructured":"Jeremy Kepner and John Gilbert . 2011. Graph Algorithms in the Language of Linear Algebra . Society for Industrial and Applied Mathematics . Jeremy Kepner and John Gilbert. 2011. Graph Algorithms in the Language of Linear Algebra. Society for Industrial and Applied Mathematics."},{"key":"e_1_2_1_18_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Symposium on the Theory of Switching. 285--292","author":"Moore Edward F.","year":"1959","unstructured":"Edward F. Moore . 1959 . The shortest path through a maze . In Proceedings of the International Symposium on the Theory of Switching. 285--292 . Edward F. Moore. 1959. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching. 285--292."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90013-X"},{"key":"e_1_2_1_21_1","first-page":"22","article-title":"Efficient breadth-first search on massively parallel and distributed-memory machines. Data Sci","volume":"2","author":"Ueno Koji","year":"2017","unstructured":"Koji Ueno , Toyotaro Suzumura , Naoya Maruyama , Katsuki Fujisawa , and Satoshi Matsuoka . 2017 . Efficient breadth-first search on massively parallel and distributed-memory machines. Data Sci . Eng. 2 , 1 (2017), 22 -- 35 . Koji Ueno, Toyotaro Suzumura, Naoya Maruyama, Katsuki Fujisawa, and Satoshi Matsuoka. 2017. Efficient breadth-first search on massively parallel and distributed-memory machines. Data Sci. Eng. 2, 1 (2017), 22--35.","journal-title":"Eng."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/16\/1\/071"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"},{"key":"e_1_2_1_24_1","volume-title":"Owens","author":"Yang Carl","year":"2019","unstructured":"Carl Yang , Aydin Buluc , and John D . Owens . 2019 . GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU. arXiv 1908.01407. arxiv:cs.DC\/1908.01407 Carl Yang, Aydin Buluc, and John D. Owens. 2019. GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU. arXiv 1908.01407. arxiv:cs.DC\/1908.01407"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Conference on Parallel Processing (ICPP \u201918)","author":"Yang Cary","unstructured":"Cary Yang , Ayd\u0131n Bulu\u00e7 , and John D. Owens . 2018. Implementing push-pull efficiently in GraphBLAS . In Proceedings of the International Conference on Parallel Processing (ICPP \u201918) . 89:1\u201389:11. Cary Yang, Ayd\u0131n Bulu\u00e7, and John D. Owens. 2018. Implementing push-pull efficiently in GraphBLAS. In Proceedings of the International Conference on Parallel Processing (ICPP \u201918). 89:1\u201389:11."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop (IPDPSW \u201915)","author":"Yang Carl","unstructured":"Carl Yang , Yangzihao Wang , and John D. Owens . 2015. Fast sparse matrix and sparse vector multiplication algorithm on the GPU . In Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop (IPDPSW \u201915) . 841--847. Carl Yang, Yangzihao Wang, and John D. Owens. 2015. Fast sparse matrix and sparse vector multiplication algorithm on the GPU. In Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop (IPDPSW \u201915). 841--847."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446216","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3446216","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:05Z","timestamp":1750193225000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,10]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3446216"],"URL":"https:\/\/doi.org\/10.1145\/3446216","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,10]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}