{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:53Z","timestamp":1750308773752,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            This paper addresses the problem of computing least-cost-path surfaces for massive grid terrains. Consider a grid terrain\n            <jats:italic>T<\/jats:italic>\n            and let\n            <jats:italic>C<\/jats:italic>\n            be a cost grid for\n            <jats:italic>T<\/jats:italic>\n            such that every point in\n            <jats:italic>C<\/jats:italic>\n            stores a value that represents the cost of traversing the corresponding point in\n            <jats:italic>T<\/jats:italic>\n            . Given\n            <jats:italic>C<\/jats:italic>\n            and a set of sources\n            <jats:italic>S<\/jats:italic>\n            \u2208\n            <jats:italic>T<\/jats:italic>\n            , a least-cost-path grid \u0394 for\n            <jats:italic>T<\/jats:italic>\n            is a grid such that every point in \u0394 represents the distance to the source in\n            <jats:italic>S<\/jats:italic>\n            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\n            <jats:italic>O<\/jats:italic>\n            (sort(\n            <jats:italic>n<\/jats:italic>\n            )) I\/Os, where sort(\n            <jats:italic>n<\/jats:italic>\n            ) is the complexity of sorting\n            <jats:italic>n<\/jats:italic>\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.\n          <\/jats:p>","DOI":"10.1145\/1227161.1370600","type":"journal-article","created":{"date-parts":[[2008,10,8]],"date-time":"2008-10-08T13:57:58Z","timestamp":1223474278000},"page":"1-31","source":"Crossref","is-referenced-by-count":5,"title":["Terracost"],"prefix":"10.1145","volume":"12","author":[{"given":"Thomas","family":"Hazel","sequence":"first","affiliation":[{"name":"Bowdoin College, Brunswick, ME"}]},{"given":"Laura","family":"Toma","sequence":"additional","affiliation":[{"name":"Bowdoin College, Brunswick, ME"}]},{"given":"Jan","family":"Vahrenhold","sequence":"additional","affiliation":[{"name":"University of Dortmund, Dortmund, Germany"}]},{"given":"Rajiv","family":"Wickremesinghe","sequence":"additional","affiliation":[{"name":"Oracle USA, Redwood Shores, CA"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/48529.48535"},{"volume-title":"Progress in Spatial Data Handling: Proceedings of the 12th International Symposium on Spatial Data Handling. Springer","author":"Agarwal P. K.","unstructured":"Agarwal, P. K., Arge, L., and Danner, A. 2006. From point cloud to grid dem: A scalable approach. In Progress in Spatial Data Handling: Proceedings of the 12th International Symposium on Spatial Data Handling. Springer, Berlin. 771--788.]]","key":"e_1_2_1_2_1"},{"volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experimentation, 3--12","author":"Ajwani D.","unstructured":"Ajwani, D., Meyer, U., and Osipov, V. 2007. Improved external memory BFS implementations. In Proceedings of the 8th Workshop on Algorithm Engineering and Experimentation, 3--12.]]","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.5555\/1109557.1109623"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.5555\/779232.779242"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1007\/s00453-003-1021-x"},{"key":"e_1_2_1_7_1","volume-title":"9th Scandinavian Workshop on Algorithm Theory, T. Hagerup and J. Katajainen, Eds. Lecture Notes in Computer Science","volume":"3111","author":"Arge L.","unstructured":"Arge, L. and Toma, L. 2004. Simplified external-memory algorithms for planar DAGs. In Algorithm Theory -- SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, T. Hagerup and J. Katajainen, Eds. Lecture Notes in Computer Science, vol. 3111. Springer, Berlin. 493--503.]]"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/945394.945395"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.5555\/645933.673356"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/777412.777427"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1016\/j.jalgor.2004.04.001"},{"unstructured":"Arge L. Barve R. D. Danner A. Hutchinson D. Molhave T. Procopiuc O. Toma L. Vahrenhold J. Vengroff D. E. and Wickremesinghe R. 2007a. TPIE user manual and reference edition 1.0. Duke University NC http:\/\/www.cs.duke.edu\/TPIE\/ (In preparation).]]","key":"e_1_2_1_12_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1137\/S0097539703428324"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1126\/science.1137521"},{"key":"e_1_2_1_15_1","volume-title":"Eds. Lecture Notes in Computer Science","volume":"2625","author":"Breimann C.","unstructured":"Breimann, C. and Vahrenhold, J. 2003. External memory computational geometry revisited. In Algorithms for Memory Hierarchies, U. Meyer, P. Sanders, and J. Sibeyn, Eds. Lecture Notes in Computer Science, vol. 2625, Chapter 6, Springer, Berlin. 110--148.]]"},{"doi-asserted-by":"publisher","unstructured":"Brengel K. Crauser A. Ferragina P. and Meyer U. 2000. An experimental study of priority queues in external memory. ACM Journal of Experimental Algorithmics 5 (Article 17).]] 10.1145\/351827.384259","key":"e_1_2_1_16_1","DOI":"10.1145\/351827.384259"},{"volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experimentation, 4--17","author":"Brodal G. S.","unstructured":"Brodal, G. S., Fagerberg, R., and Vinther, K. 2004. Engineering cache-oblivious sorting algorithms. In Proceedings of the 6th Workshop on Algorithm Engineering and Experimentation, 4--17.]]","key":"e_1_2_1_17_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1007\/11523468_47"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.5555\/1109557.1109614"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.5555\/314464.314638"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.5555\/313651.313681"},{"volume-title":"Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science. 195--208","author":"Dementiev R.","unstructured":"Dementiev, R., Sanders, P., Schultes, D., and Sibeyn, J. F. 2004. Engineering an external memory minimum spanning tree algorithm. In Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science. 195--208.]]","key":"e_1_2_1_22_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1007\/11561071_57"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1007\/BF01386390"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/367766.368168"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/355588.365103"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.5555\/795665.796479"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.5555\/646344.689749"},{"volume-title":"Proceedings of the 7th Workshop on Algorithm Engineering and Experiments. 15 pp.]]","author":"Goldberg A. V.","unstructured":"Goldberg, A. V. and Werneck, R. F. 2005. An efficient external memory shortest path algorithm. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments. 15 pp.]]","key":"e_1_2_1_29_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.5555\/1070432.1070455"},{"volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. 15 pp.]]","author":"Goldberg A. V.","unstructured":"Goldberg, A. V., Kaplan, H., and Werneck, R. F. 2006. Reach for A&ast;: Efficient point-to-point shortest path algorithms. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. 15 pp.]]","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. 100--111","author":"Gutman R.","year":"2004","unstructured":"Gutman, R. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. 100--111.]]"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1006\/jcss.1997.1493"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1145\/1064546.1180616"},{"volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. 156--170","author":"Holzer M.","unstructured":"Holzer, M., Schulz, F., and Wagner, D. 2006. Engineering multi-level overlay graphs for shortest-path queries. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. 156--170.]]","key":"e_1_2_1_35_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1007\/11523468_46"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.5555\/1070432.1070454"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.5555\/280635"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1007\/11427186_13"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.5555\/1032647.1033314"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.5555\/829517.830723"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1145\/235141.235145"},{"volume-title":"Proceedings of the 11th International Conference Parallel and Distributed Computing and Systems. 454--460","author":"Lambert O.","unstructured":"Lambert, O. and Sibeyn, J. F. 1999. Parallel and external list ranking and connected components on a cluster of workstations. In Proceedings of the 11th International Conference Parallel and Distributed Computing and Systems. 454--460.]]","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","first-page":"219","article-title":"An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilit\u00e4t -- von der Forschung zur praktischen Anwendung. Beitr\u00e4ge zu den M\u00fcnsteraner GI-Tagen","volume":"22","author":"Lauther U.","year":"2004","unstructured":"Lauther, U. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilit\u00e4t -- von der Forschung zur praktischen Anwendung. Beitr\u00e4ge zu den M\u00fcnsteraner GI-Tagen. IfGI Prints, vol. 22. 219--230.]]","journal-title":"IfGI Prints"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.5555\/646342.686750"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.5555\/545381.545430"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.5555\/647912.740673"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 11th European Symposium on Algorithms, G. Di Battista and U. Zwick, Eds. Lecture Notes in Computer Science","volume":"2832","author":"Meyer U.","unstructured":"Meyer, U. and Zeh, N. 2003. I\/O-efficient undirected shortest paths. In Proceedings of the 11th European Symposium on Algorithms, G. Di Battista and U. Zwick, Eds. Lecture Notes in Computer Science, vol. 2832. Springer, Berlin. 434--445.]]"},{"doi-asserted-by":"publisher","key":"e_1_2_1_49_1","DOI":"10.1007\/11841036_49"},{"doi-asserted-by":"publisher","key":"e_1_2_1_50_1","DOI":"10.1007\/11427186_18"},{"doi-asserted-by":"publisher","key":"e_1_2_1_51_1","DOI":"10.1016\/S0304-3975(03)00402-X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_52_1","DOI":"10.5555\/545381.545417"},{"doi-asserted-by":"publisher","key":"e_1_2_1_53_1","DOI":"10.1137\/S0097539702419650"},{"doi-asserted-by":"publisher","key":"e_1_2_1_54_1","DOI":"10.5555\/646680.702326"},{"doi-asserted-by":"publisher","unstructured":"Sanders P. 2000. Fast priority queues for cached memory. ACM Journal on Experimental Algorithmics 5 (Article 7).]] 10.1145\/351827.384249","key":"e_1_2_1_55_1","DOI":"10.1145\/351827.384249"},{"doi-asserted-by":"publisher","key":"e_1_2_1_56_1","DOI":"10.1145\/564870.564917"},{"doi-asserted-by":"publisher","key":"e_1_2_1_57_1","DOI":"10.5555\/795663.796356"},{"doi-asserted-by":"publisher","key":"e_1_2_1_58_1","DOI":"10.1145\/384192.384193"},{"volume-title":"Proceedings of the 7th Workshop on Algorithm Engineering and Experiments. 15--24","author":"Wagner D.","unstructured":"Wagner, D. and Willhalm, T. 2005. Drawing graphs to speed up shortest-path computations. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments. 15--24.]]","key":"e_1_2_1_59_1"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1370600","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1370600","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1370600"}},"subtitle":["Computing least-cost-path surfaces for massive grid terrains"],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":59,"alternative-id":["10.1145\/1227161.1370600"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1370600","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}