Cache-Oblivious Shortest Paths in Graphs Using Buffer Heap

Rezaul Alam Chowdhury and Vijaya Ramachandran

Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004), Barcelona, Spain, pp. 245-254, 2004


We present the Buffer Heap (BH), a cache-oblivious priority queue that supports Delete-Min, Delete, and Decrease-Key operations in O((1/B)log(N/B)) 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 = Ω(B^(1 + ε)), 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 + (E/B)log(V/B)) block transfers and for the directed case performs O((V + E/B)log(V/B)) 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.

Download (copyright restrictions may apply): PSPDF