Name
Title | ||
|---|---|---|
An Empirical Study of Cache-Oblivious Priority Queues and their Application to the Shortest Path Problem |
Abstract | ||
|---|---|---|
In recent years the Cache-Oblivious model of external mem- ory computation has provided an attractive theoretical basis for the anal- ysis of algorithms on massive datasets. Much progress has been made in discovering algorithms that are asymptotically optimal or near optimal. However, to date there are still relatively few successful experimental studies. In this paper we compare two dierent Cache-Oblivious priority queues based on the Funnel and Bucket Heap and apply them to the sin- gle source shortest path problem on graphs with positive edge weights. Our results show that when RAM is limited and data is swapping to external storage, the Cache-Oblivious priority queues achieve orders of magnitude speedups over standard internal memory techniques. How- ever, for the single source shortest path problem both on simulated and real world graph data, these speedups are markedly lower due to the time required to access the graph adjacency list itself. |
Year | Venue | Keywords |
|---|---|---|
2008 | Clinical Orthopaedics and Related Research | software engineering,empirical study,priority queue,shortest path problem,data structure |
Field | DocType | Volume |
Canadian traveller problem,Combinatorics,Shortest path problem,Computer science,Constrained Shortest Path First,Priority queue,Shortest Path Faster Algorithm,Longest path problem,Widest path problem,K shortest path routing | Journal | abs/0802.1 |
Citations | PageRank | References |
3 | 0.37 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Benjamin Sach | 1 | 93 | 11.40 |
| Raphaël Clifford | 2 | 268 | 28.57 |