Buffer Heap: A Cache-Oblivious Priority Queue with Applications to Shortest Path Computations

Vijaya Ramachandran
University of Texas at Austin

Friday, October 27th, 2006, 3:30 pm
Wean Hall 7220

Abstract

We present the Buffer Heap (BH), a cache-oblivious priority queue that supports all traditional priority queue operations as well as the Decrease-Key operation in O((1/B) log n) amortized block transfers (or I/Os) per operation, where B is the (unknown) block size and n is the number of elements on the BH. Using the BH we present shortest path methods based on Dijkstra's algorithm that are theoretically superior to traditional methods in terms of the number of I/Os performed.

We present experimental results that indicate that BH is faster than other general-purpose priority queues when the number of priority queue operations is reasonably large. We also present experimental results that show that shortest path methods that use BH and its variants are faster on some natural classes of graphs than Dijkstra's algorithm with traditional general-purpose priority queues.

This is joint work with Rezaul Alam Chowdhury; additionally, Lingling Tong and David Lan Roche contributed to the experimental work.