From everywhere to everywhere (Fete): Adaptation of a pedestrian movement network model to a hybrid parallel environment

Alexandre Sorokine; Devin White; Andrew Hardin

doi:10.1007/978-3-319-22786-3_31

From everywhere to everywhere (Fete): Adaptation of a pedestrian movement network model to a hybrid parallel environment

Alexandre Sorokine, Devin White, Andrew Hardin

Geospatial Data Modeling

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

Shortest-path algorithms are hard to parallelize because they require a large number of global operations to estimate the costs of alternative routes. However, some geographic problems, such as locating archaeological sites and tracking the spread of infectious diseases, demand the ability to find a large number of the shortest paths on very large graphs or grids. Here, we present an approach based on the out-of-RAM Dijkstra shortest-path algorithm that can be employed in hybrid massively parallel or cloud environments. In this approach, we partition the graph, precompute all paths inside each partition, and then assemble the routes from precomputed paths. We demonstrate the utility of this approach by estimating travel frequency in pedestrian networks.

Original language	English
Title of host publication	Advances in Geocomputation - Geocomputation 2015—The 13th International Conference
Editors	Daniel A. Griffith, Yongwan Chun, Denis J. Dean
Publisher	Springer Heidelberg
Pages	347-353
Number of pages	7
ISBN (Print)	9783319227856
DOIs	https://doi.org/10.1007/978-3-319-22786-3_31
State	Published - 2017
Event	13th International Conference on Advances in Geocomputation, Geocomputation 2015 - Dallas, United States Duration: May 20 2015 → May 23 2015

Publication series

Name	Advances in Geographic Information Science
ISSN (Print)	1867-2434
ISSN (Electronic)	1867-2442

Conference

Conference	13th International Conference on Advances in Geocomputation, Geocomputation 2015
Country/Territory	United States
City	Dallas
Period	05/20/15 → 05/23/15

Funding

This manuscript has been authored by employees of UT-Battelle, LLC, under contract DE-AC05-00OR22725 with the U.S. Department of Energy. Accordingly, the United States Government retains, and the publisher, by accepting the article for publication, acknowledges that the United States Government retains, a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes.

Keywords

Hybrid parallelization
Population movement
Single source shortest path

Access to Document

10.1007/978-3-319-22786-3_31

Cite this

Sorokine, A., White, D., & Hardin, A. (2017). From everywhere to everywhere (Fete): Adaptation of a pedestrian movement network model to a hybrid parallel environment. In D. A. Griffith, Y. Chun, & D. J. Dean (Eds.), Advances in Geocomputation - Geocomputation 2015—The 13th International Conference (pp. 347-353). (Advances in Geographic Information Science). Springer Heidelberg. https://doi.org/10.1007/978-3-319-22786-3_31

Sorokine, Alexandre ; White, Devin ; Hardin, Andrew. / From everywhere to everywhere (Fete) : Adaptation of a pedestrian movement network model to a hybrid parallel environment. Advances in Geocomputation - Geocomputation 2015—The 13th International Conference. editor / Daniel A. Griffith ; Yongwan Chun ; Denis J. Dean. Springer Heidelberg, 2017. pp. 347-353 (Advances in Geographic Information Science).

@inproceedings{3be75a0ca15f4b4cb7c2b3c0aef3901d,

title = "From everywhere to everywhere (Fete): Adaptation of a pedestrian movement network model to a hybrid parallel environment",

abstract = "Shortest-path algorithms are hard to parallelize because they require a large number of global operations to estimate the costs of alternative routes. However, some geographic problems, such as locating archaeological sites and tracking the spread of infectious diseases, demand the ability to find a large number of the shortest paths on very large graphs or grids. Here, we present an approach based on the out-of-RAM Dijkstra shortest-path algorithm that can be employed in hybrid massively parallel or cloud environments. In this approach, we partition the graph, precompute all paths inside each partition, and then assemble the routes from precomputed paths. We demonstrate the utility of this approach by estimating travel frequency in pedestrian networks.",

keywords = "Hybrid parallelization, Population movement, Single source shortest path",

author = "Alexandre Sorokine and Devin White and Andrew Hardin",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2017.; 13th International Conference on Advances in Geocomputation, Geocomputation 2015 ; Conference date: 20-05-2015 Through 23-05-2015",

year = "2017",

doi = "10.1007/978-3-319-22786-3_31",

language = "English",

isbn = "9783319227856",

series = "Advances in Geographic Information Science",

publisher = "Springer Heidelberg",

pages = "347--353",

editor = "Griffith, {Daniel A.} and Yongwan Chun and Dean, {Denis J.}",

booktitle = "Advances in Geocomputation - Geocomputation 2015—The 13th International Conference",

}

Sorokine, A, White, D & Hardin, A 2017, From everywhere to everywhere (Fete): Adaptation of a pedestrian movement network model to a hybrid parallel environment. in DA Griffith, Y Chun & DJ Dean (eds), Advances in Geocomputation - Geocomputation 2015—The 13th International Conference. Advances in Geographic Information Science, Springer Heidelberg, pp. 347-353, 13th International Conference on Advances in Geocomputation, Geocomputation 2015, Dallas, United States, 05/20/15. https://doi.org/10.1007/978-3-319-22786-3_31

From everywhere to everywhere (Fete): Adaptation of a pedestrian movement network model to a hybrid parallel environment. / Sorokine, Alexandre; White, Devin; Hardin, Andrew.
Advances in Geocomputation - Geocomputation 2015—The 13th International Conference. ed. / Daniel A. Griffith; Yongwan Chun; Denis J. Dean. Springer Heidelberg, 2017. p. 347-353 (Advances in Geographic Information Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - From everywhere to everywhere (Fete)

T2 - 13th International Conference on Advances in Geocomputation, Geocomputation 2015

AU - Sorokine, Alexandre

AU - White, Devin

AU - Hardin, Andrew

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2017.

PY - 2017

Y1 - 2017

N2 - Shortest-path algorithms are hard to parallelize because they require a large number of global operations to estimate the costs of alternative routes. However, some geographic problems, such as locating archaeological sites and tracking the spread of infectious diseases, demand the ability to find a large number of the shortest paths on very large graphs or grids. Here, we present an approach based on the out-of-RAM Dijkstra shortest-path algorithm that can be employed in hybrid massively parallel or cloud environments. In this approach, we partition the graph, precompute all paths inside each partition, and then assemble the routes from precomputed paths. We demonstrate the utility of this approach by estimating travel frequency in pedestrian networks.

AB - Shortest-path algorithms are hard to parallelize because they require a large number of global operations to estimate the costs of alternative routes. However, some geographic problems, such as locating archaeological sites and tracking the spread of infectious diseases, demand the ability to find a large number of the shortest paths on very large graphs or grids. Here, we present an approach based on the out-of-RAM Dijkstra shortest-path algorithm that can be employed in hybrid massively parallel or cloud environments. In this approach, we partition the graph, precompute all paths inside each partition, and then assemble the routes from precomputed paths. We demonstrate the utility of this approach by estimating travel frequency in pedestrian networks.

KW - Hybrid parallelization

KW - Population movement

KW - Single source shortest path

UR - http://www.scopus.com/inward/record.url?scp=85010046912&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-22786-3_31

DO - 10.1007/978-3-319-22786-3_31

M3 - Conference contribution

AN - SCOPUS:85010046912

SN - 9783319227856

T3 - Advances in Geographic Information Science

SP - 347

EP - 353

BT - Advances in Geocomputation - Geocomputation 2015—The 13th International Conference

A2 - Griffith, Daniel A.

A2 - Chun, Yongwan

A2 - Dean, Denis J.

PB - Springer Heidelberg

Y2 - 20 May 2015 through 23 May 2015

ER -

Sorokine A, White D, Hardin A. From everywhere to everywhere (Fete): Adaptation of a pedestrian movement network model to a hybrid parallel environment. In Griffith DA, Chun Y, Dean DJ, editors, Advances in Geocomputation - Geocomputation 2015—The 13th International Conference. Springer Heidelberg. 2017. p. 347-353. (Advances in Geographic Information Science). doi: 10.1007/978-3-319-22786-3_31

From everywhere to everywhere (Fete): Adaptation of a pedestrian movement network model to a hybrid parallel environment

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this