{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:37Z","timestamp":1750221277556,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,1,3]],"date-time":"2018-01-03T00:00:00Z","timestamp":1514937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCR-9988160, CCF-1320675, CCF-1439084 and CNS-1553510"],"award-info":[{"award-number":["CCR-9988160, CCF-1320675, CCF-1439084 and CNS-1553510"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"MCD Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,1,31]]},"abstract":"<jats:p>\n            We present the\n            <jats:italic>buffer heap<\/jats:italic>\n            , a cache-oblivious priority queue that supports\n            <jats:italic>Delete-Min<\/jats:italic>\n            ,\n            <jats:italic>Delete<\/jats:italic>\n            , and a hybrid\n            <jats:italic>Insert<\/jats:italic>\n            \/\n            <jats:italic>Decrease-Key<\/jats:italic>\n            operation in\n            <jats:italic>O<\/jats:italic>\n            (1\/\n            <jats:italic>B<\/jats:italic>\n            log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>N<\/jats:italic>\n            \/\n            <jats:italic>M<\/jats:italic>\n            ) amortized block transfers from main memory, where\n            <jats:italic>M<\/jats:italic>\n            and\n            <jats:italic>B<\/jats:italic>\n            are the (unknown) cache size and block size, respectively, and\n            <jats:italic>N<\/jats:italic>\n            is the number of elements in the queue. We introduce the notion of a\n            <jats:italic>slim data structure<\/jats:italic>\n            that captures the situation when only a limited portion of the cache, which we call a\n            <jats:italic>slim cache<\/jats:italic>\n            , is available to the data structure to retain data between data structural operations. We show that a buffer heap automatically adapts to such an environment and supports all operations in\n            <jats:italic>O<\/jats:italic>\n            (1\/\u03bb + 1\/\n            <jats:italic>B<\/jats:italic>\n            log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>N<\/jats:italic>\n            \/\u03bb) amortized block transfers each when the size of the slim cache is \u03bb. Our results provide substantial improvements over known trivial cache performance bounds for cache-oblivious priority queues with\n            <jats:italic>Decrease-Keys<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Using the buffer heap, we present cache-oblivious implementations of Dijkstra\u2019s algorithm for undirected and directed single-source shortest path (SSSP) problems for graphs with non-negative real edge-weights. On a graph with\n            <jats:italic>n<\/jats:italic>\n            vertices and\n            <jats:italic>m<\/jats:italic>\n            edges, our algorithm for the undirected case performs\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>M<\/jats:italic>\n            ) block transfers and for the directed case performs\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            ) \u010b log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            ) block transfers. These results give the first non-trivial cache-oblivious bounds for the SSSP problem on general graphs. For the all-pairs shortest path (APSP) problem on weighted undirected graphs, we incorporate slim buffer heaps into multi-buffer-buffer-heaps and use these to improve the cache-aware cache complexity. We also present a simple cache-oblivious APSP algorithm for unweighted undirected graphs that performs\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            log\n            <jats:sub>\n              <jats:italic>M<\/jats:italic>\n              \/\n              <jats:italic>B<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            ) block transfers. This matches the cache-aware bound and is a substantial improvement over the previous cache-oblivious bound for the problem.\n          <\/jats:p>","DOI":"10.1145\/3147172","type":"journal-article","created":{"date-parts":[[2018,1,4]],"date-time":"2018-01-04T16:27:31Z","timestamp":1515083251000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Cache-Oblivious Buffer Heap and Cache-Efficient Computation of Shortest Paths in Graphs"],"prefix":"10.1145","volume":"14","author":[{"given":"Rezaul A.","family":"Chowdhury","sequence":"first","affiliation":[{"name":"University of Texas at Austin"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703428324"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2013.6691597"},{"volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages, and Programming. 146--157","author":"Arge L.","key":"e_1_2_1_4_1","unstructured":"L. Arge , U. Meyer , and L. Toma . 2004. External-memory algorithms for diameter and all-pairs shortest-paths on sparse graphs . In Proceedings of the 31st International Colloquium on Automata, Languages, and Programming. 146--157 . L. Arge, U. Meyer, and L. Toma. 2004. External-memory algorithms for diameter and all-pairs shortest-paths on sparse graphs. In Proceedings of the 31st International Colloquium on Automata, Languages, and Programming. 146--157."},{"volume-title":"Proceedings of the 13th Annual International Symposium on Algorithms and Computation (LNCS 2518)","author":"Brodal G. S.","key":"e_1_2_1_5_1","unstructured":"G. S. Brodal and R. Fagerberg . 2002. Funnel heap -- A cache oblivious priority queue . In Proceedings of the 13th Annual International Symposium on Algorithms and Computation (LNCS 2518) . Springer-Verlag, Vancouver, BC, Canada, 219--228. G. S. Brodal and R. Fagerberg. 2002. Funnel heap -- A cache oblivious priority queue. In Proceedings of the 13th Annual International Symposium on Algorithms and Computation (LNCS 2518). Springer-Verlag, Vancouver, BC, Canada, 219--228."},{"volume-title":"Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory. 480--492","author":"Brodal G. S.","key":"e_1_2_1_6_1","unstructured":"G. S. Brodal , R. Fagerberg , U. Meyer , and N. Zeh . 2004. Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths . In Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory. 480--492 . G. S. Brodal, R. Fagerberg, U. Meyer, and N. Zeh. 2004. Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths. In Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory. 480--492."},{"volume-title":"Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms. 859--860","author":"Buchsbaum A. L.","key":"e_1_2_1_7_1","unstructured":"A. L. Buchsbaum , M. Goldwasser , S. Venkatasubramanian , and J. R. Westbrook . 2000. On external memory graph traversal . In Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms. 859--860 . A. L. Buchsbaum, M. Goldwasser, S. Venkatasubramanian, and J. R. Westbrook. 2000. On external memory graph traversal. In Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms. 859--860."},{"volume-title":"Measuring and Improving the Performance of Cache-efficient Priority Queues in Dijkstra\u2019s Algorithm. Undergraduate Honors Thesis. Report# HR-07-36. Computer Science Department","author":"Chen M.","key":"e_1_2_1_8_1","unstructured":"M. Chen . 2007. Measuring and Improving the Performance of Cache-efficient Priority Queues in Dijkstra\u2019s Algorithm. Undergraduate Honors Thesis. Report# HR-07-36. Computer Science Department , University of Texas at Austin. M. Chen. 2007. Measuring and Improving the Performance of Cache-efficient Priority Queues in Dijkstra\u2019s Algorithm. Undergraduate Honors Thesis. Report# HR-07-36. Computer Science Department, University of Texas at Austin."},{"key":"e_1_2_1_9_1","volume-title":"Technical Report TR-07-54. Computer Science Department","author":"Chen M.","year":"2007","unstructured":"M. Chen , R. A. Chowdhury , V. Ramachandran , D. Roche , and L. Tong . 2007 . Priority Queues and Dijkstra\u2019s Algorithm . Technical Report TR-07-54. Computer Science Department , University of Texas at Austin. M. Chen, R. A. Chowdhury, V. Ramachandran, D. Roche, and L. Tong. 2007. Priority Queues and Dijkstra\u2019s Algorithm. Technical Report TR-07-54. Computer Science Department, University of Texas at Austin."},{"volume-title":"Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms. 139--149","author":"Chiang Y. J.","key":"e_1_2_1_10_1","unstructured":"Y. J. Chiang , M. T. Goodrich , E. F. Grove , R. Tamassia , D. E. Vengroff , and J. S. Vitter . 1995. External-memory graph algorithms . In Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms. 139--149 . Y. J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. 1995. External-memory graph algorithms. In Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms. 139--149."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007949"},{"volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms","author":"Chowdhury R. A.","key":"e_1_2_1_12_1","unstructured":"R. A. Chowdhury and V. Ramachandran . 2005. External-memory exact and approximate all-pairs shortest paths in undirected graphs . In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms . Vancouver, BC, Canada, 735--744. R. A. Chowdhury and V. Ramachandran. 2005. External-memory exact and approximate all-pairs shortest paths in undirected graphs. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. Vancouver, BC, Canada, 735--744."},{"volume-title":"Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms. 591--600","author":"Chowdhury R. A.","key":"e_1_2_1_13_1","unstructured":"R. A. Chowdhury and V. Ramachandran . 2006. Cache-oblivious dynamic programming . In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms. 591--600 . R. A. Chowdhury and V. Ramachandran. 2006. Cache-oblivious dynamic programming. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms. 591--600."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1224-z"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055437"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071383"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"I. Katriel and U. Meyer. 2003. Elementary graph algorithms in external memory. In Algorithms for Memory Hierarchies U. Meyer P. Sanders and J. F. Sibeyn (Eds.). Springer-Verlag 62--84.  I. Katriel and U. Meyer. 2003. Elementary graph algorithms in external memory. In Algorithms for Memory Hierarchies U. Meyer P. Sanders and J. F. Sibeyn (Eds.). Springer-Verlag 62--84.","DOI":"10.1007\/3-540-36574-5_4"},{"volume-title":"Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing. 169--177","author":"Kumar V.","key":"e_1_2_1_20_1","unstructured":"V. Kumar and E. Schwabe . 1996. Improved algorithms and data structures for solving graph problems in external memory . In Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing. 169--177 . V. Kumar and E. Schwabe. 1996. Improved algorithms and data structures for solving graph problems in external memory. In Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing. 169--177."},{"volume-title":"Proceedings of the 11th European Symposium on Algorithms (LNCS 2832)","author":"Meyer U.","key":"e_1_2_1_21_1","unstructured":"U. Meyer and N. Zeh . 2003. I\/O-efficient undirected shortest paths . In Proceedings of the 11th European Symposium on Algorithms (LNCS 2832) . Springer-Verlag, 434--445. U. Meyer and N. Zeh. 2003. I\/O-efficient undirected shortest paths. In Proceedings of the 11th European Symposium on Algorithms (LNCS 2832). Springer-Verlag, 434--445."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_49"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229163.2229166"},{"volume-title":"Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms. 687--694","author":"Munagala K.","key":"e_1_2_1_24_1","unstructured":"K. Munagala and A. Ranade . 1999. I\/O-complexity of graph algorithms . In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms. 687--694 . K. Munagala and A. Ranade. 1999. I\/O-complexity of graph algorithms. In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms. 687--694."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.44"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00402-X"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702419650"},{"key":"e_1_2_1_28_1","unstructured":"H. Prokop. 1999. Cache-Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science MIT.  H. Prokop. 1999. Cache-Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science MIT."},{"volume-title":"Experimental Study of High Performance Priority Queues. Undergraduate Honors Thesis. Report# HR-07-34. Computer Science Department","author":"Roche D. L.","key":"e_1_2_1_29_1","unstructured":"D. L. Roche . 2007. Experimental Study of High Performance Priority Queues. Undergraduate Honors Thesis. Report# HR-07-34. Computer Science Department , University of Texas at Austin. D. L. Roche. 2007. Experimental Study of High Performance Priority Queues. Undergraduate Honors Thesis. Report# HR-07-34. Computer Science Department, University of Texas at Austin."},{"key":"e_1_2_1_30_1","unstructured":"B. Sach and R. Clifford. 2008. An empirical study of cache-oblivious priority queues and their application to the shortest path problem. CoRR abs\/0802.1026 (2008). http:\/\/arxiv.org\/abs\/0802.1026.  B. Sach and R. Clifford. 2008. An empirical study of cache-oblivious priority queues and their application to the shortest path problem. CoRR abs\/0802.1026 (2008). http:\/\/arxiv.org\/abs\/0802.1026."},{"volume-title":"Implementation and Experimental Evaluation of the Cache-oblivious Buffer Heap. Undergraduate Honors Thesis. Report# HR-06-21. Computer Science Department","author":"Tong L.","key":"e_1_2_1_31_1","unstructured":"L. Tong . 2006. Implementation and Experimental Evaluation of the Cache-oblivious Buffer Heap. Undergraduate Honors Thesis. Report# HR-06-21. Computer Science Department , University of Texas at Austin. L. Tong. 2006. Implementation and Experimental Evaluation of the Cache-oblivious Buffer Heap. Undergraduate Honors Thesis. Report# HR-06-21. Computer Science Department, University of Texas at Austin."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000014"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3147172","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3147172","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3147172","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:15Z","timestamp":1750212675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3147172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,3]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,31]]}},"alternative-id":["10.1145\/3147172"],"URL":"https:\/\/doi.org\/10.1145\/3147172","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,1,3]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}