Thumbnail
Access Restriction
Subscribed

Author Hazel, Thomas ♦ Toma, Laura ♦ Vahrenhold, Jan ♦ Wickremesinghe, Rajiv
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Data structures and algorithms ♦ Dijkstra's algorithm ♦ I/O-efficiency ♦ Shortest paths ♦ Terrain data
Abstract This paper addresses the problem of computing least-cost-path surfaces for massive grid terrains. Consider a grid terrain $\textit{T}$ and let $\textit{C}$ be a cost grid for $\textit{T}$ such that every point in $\textit{C}$ stores a value that represents the cost of traversing the corresponding point in $\textit{T}.$ Given $\textit{C}$ and a set of sources $\textit{S}$ ∈ $\textit{T},$ a least-cost-path grid Δ for $\textit{T}$ is a grid such that every point in Δ represents the distance to the source in $\textit{S}$ that can be reached with minimal cost. We present a scalable approach to computing least-cost-path grids. Our algorithm, terracost, is derived from our previous work on I/O-efficient shortest paths on grids and uses $\textit{O}(sort(\textit{n}))$ I/Os, where $sort(\textit{n})$ is the complexity of sorting $\textit{n}$ items of data in the I/O-model of Aggarwal and Vitter. We present the design, the analysis, and an experimental study of terracost. An added benefit of the algorithm underlying terracost is that it naturally lends itself to parallelization. We have implemented terracost in a distributed environment using our cluster management tool and report on experiments that show that it obtains speedup near-linear with the size of the cluster. To the best of our knowledge, this is the first experimental evaluation of a multiple-source least-cost-path algorithm in the external memory setting.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-06-12
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 12
Page Count 31
Starting Page 1
Ending Page 31


Open content in new tab

   Open content in new tab
Source: ACM Digital Library