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(_B¹ log_{2 M}^N ) amortized block transfers from main memory, where M and B are the (unknown) cache size and block size, respectively, and N is the number of elements in the queue. We introduce the notion of a slim data structure that captures the situation when only a limited portion of the cache, which we call a slim cache, 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 O(_λ¹ +_B¹ log₂^N_λ ) amortized block transfers each when the size of the slim cache is λ. Our results provide substantial improvements over known trivial cache performance bounds for cache-oblivious priority queues with Decrease-Keys. Using the buffer heap, we present cache-oblivious implementations of Dijkstra’s algorithm for undirected and directed single-source shortest path (SSSP) problems for graphs with non-negative real edge-weights. On a graph with n vertices and m edges, our algorithm for the undirected case performs O(n +^m_B log_{2 M}ⁿ ) block transfers and for the directed case performs O((n + ^m_B ) · log_{2 B}ⁿ ) 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 O(^mn_B log_M/B _Bⁿ ) block transfers. This matches the cache-aware bound and is a substantial improvement over the previous cache-oblivious bound for the problem.