Terracost: Computing least-cost-path surfaces for massive grid terrainsTerracost: Computing least-cost-path surfaces for massive grid terrains

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

Source: ACM Digital Library