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 log(2) N/M) 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(1/lambda + 1/B log(2) N/lambda) amortized block transfers each when the size of the slim cache is lambda. Our results provide substantial improvements over known trivial cache performance bounds for cache-oblivious priority queues with Decrease-Keys.