Name
Abstract | ||
|---|---|---|
Multiresolution priority queues are recently introduced data structures that can trade-off a small bounded error for faster performance. When used to implement the frontier set in label setting algorithms, they provide a new mathematical approach to classic graph problems such as the computation of shortest paths or minimum spanning trees. To understand how they work, this paper presents a mathematical study of multiresolution label setting algorithms. The theory is general in that the classic mathematical results respond to the particular case where the problem's resolution is infinitely small. The concept of multiresolution helps break the information theoretic barriers of the problem by achieving lower time complexity at the cost of introducing a bounded error. Such error is proven independent of the graph size, a relevant feature in uniform-cost search algorithms where graphs can be infinitely large. Properly tuned, Dijkstra's multiresolution algorithm delivers an amortized cost of O(|V|+|E|), where V and E are the set of vertices and edges, respectively. Benchmarks show speedups of 53% and 26% when applied to Dijkstra's and A* algorithms on a graph of US roads with 87,575 vertices and 121,961 edges. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/HPEC.2018.8547539 | 2018 IEEE High Performance extreme Computing Conference (HPEC) |
Keywords | Field | DocType |
Dijkstra multiresolution algorithm,graph size,classic mathematical results,multiresolution label,mathematical study,minimum spanning trees,shortest paths,classic graph problems,mathematical approach,label setting algorithms,frontier set,faster performance,bounded error,data structures,multiresolution priority queues,uniform-cost search algorithms | Convergence (routing),Data structure,Search algorithm,Vertex (geometry),Computer science,Algorithm,Priority queue,Spanning tree,Time complexity,Dijkstra's algorithm | Conference |
ISSN | ISBN | Citations |
2377-6943 | 978-1-5386-5990-8 | 0 |
PageRank | References | Authors |
0.34 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jordi Ros-Giralt | 1 | 3 | 2.14 |
| Alan Commike | 2 | 5 | 3.25 |
| Peter Cullen | 3 | 1 | 0.71 |
| Richard Lethin | 4 | 118 | 17.17 |