Rezaul Alam Chowdhury
ABSTRACT
We present the Buffer Heap (BH), a cache-oblivious priority queue that supports Delete-Min, Delete, and Decrease-Key operations in O(1overB log2 NoverB) amortized block transfers from external memory, where B is the (unknown) block-size and N is the maximum number of elements in the queue. As is common in cache-oblivious algorithms, we assume a 'tall cache' (i.e., M = Ω(B1 + ε), where M is the size of the main memory). We also assume the Decrease-Key operation only verifies that the element does not exist in the priority queue with a smaller key value, hence it also supports the insert operation in the same amortized bound. The amortized time bound for each operation is O(log N). We also present a Cache-Oblivious Tournament Tree (COTT), which is simpler than the Buffer Heap, but has weaker bounds.Using the Buffer Heap we present cache-oblivious algorithms for undirected and directed single-source shortest path (SSSP) problems for graphs with non-negative edge-weights. On a graph with V vertices and E edges, our algorithm for the undirected case performs O(V + EoverB log2 VoverB) block transfers and for the directed case performs O((V + EoverB) . log2 VoverB) block transfers. The running time of both algorithms is O((V + E). log V).For both priority queues with Decrease-Key operation, and for shortest path problems on general graphs, our results appear to give the first non-trivial cache-oblivious bounds.
- A. Aggarwal and J.S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31:1116--1127, 1988. Google Scholar
Digital Library
- L. Arge, M. A. Bender, E. D. Demaine, B. Holland-Minkley, and J. I. Munro. Cache-oblivious priority queue and graph algorithm applications. In Proceedings of ACM Symposium on Theory of Computing, pp. 268--276, May 2002. Google ScholarDigital Library
- G.S. Brodal and R. Fagerberg. Funnel heap -- a cache oblivious priority queue. In Proceedings of the 13th Annual International Symposium on Algorithms and Computation, LNCS 2518, pp. 219--228, Nov. 2002. Google ScholarDigital Library
- G.S. Brodal, R. Fagerberg, U. Meyer, and N. Zeh. Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths. To appear in Proceedings of the 9th Scandinavian Workshop on Algorithm Theory, July 2004.Google Scholar
- A. L. Buchsbaum, M. Goldwasser, S. Venkatasubramanian, and J. R. Westbrook. On external memory graph traversal. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 859--860, 2000. Google ScholarDigital Library
- Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 139--149, 1995. Google ScholarDigital Library
- E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.Google ScholarDigital Library
- M.L. Fredman and R.E. Tarjan. Fibonacci heaps and their use in improved network optimization algorithms. Journal of the ACM, 34:596--615, 1987. Google ScholarDigital Library
- M. Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pp. 285--297, 1999. Google ScholarDigital Library
- I. Katriel and U. Meyer. Elementary graph algorithms in external memory. In U. Meyer, P. Sanders, and J.F. Sibeyn, editors, Algorithms for Memory Hierarchies, LNCS 2625. Springer, 2003.Google Scholar
- V. Kumar and E. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In Proceedings of the IEEE Symposium on Parallel and Distributed Processing, pp. 169--177, 1996. Google ScholarDigital Library
- U. Meyer and N. Zeh. I/O-efficient undirected shortest paths. In Proceedings of the European Symposium on Algorithms, LNCS 2832, pp. 434--445, Sep. 2003.Google ScholarCross Ref
- S. Pettie and V. Ramachandran. Computing shortest paths with comparisons and additions. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 713--722, San Francisco, CA, 2002. Google ScholarDigital Library
- H. Prokop. Cache-oblivious algorithms. Master's thesis, Department of Electrical Engineering and Computer Science, MIT, June 1999.Google Scholar
- J.S. Vitter. External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys, 33(2):209--271, 2001. Google ScholarDigital Library
Index Terms
- Cache-oblivious shortest paths in graphs using buffer heap
Recommendations
Cache-Oblivious Buffer Heap and Cache-Efficient Computation of Shortest Paths in Graphs
We present the buffer heap, a cache-oblivious priority queue that supports Delete-Min, Delete, and a hybrid Insert/Decrease-Key operation in O(1/B log2 N/M) amortized block transfers from main memory, where M and B are the (unknown) cache size and block ...
All-pairs shortest paths for unweighted undirected graphs in o(mn) time
We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times:
{ O(mn/log n) if m > n log n log log log n O(mn log log n/log n) if m > n log log ...
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of ComputingWe present a deterministic (1+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (...
Comments