Fast Analysis of Upstream Features on Spatial Networks (GIS Cup) | W. Randolph Franklin, Rensselaer Polytechnic Institute, Troy NY USA

Salles Viana Gomes de Magalhães, W. Randolph Franklin, and Ricardo dos Santos Ferreira. Fast analysis of upstream features on spatial networks (GIS Cup). In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '18, 622–625. New York, NY, USA, 2018. ACM. Winner (1st place). doi:https://doi.org/10.1145/3274895.3276474.
[full text] [slides] [BibTeX▼]

@inproceedings{salles-giscup-2018,
    author = "de Magalhães, Salles Viana Gomes and Franklin, W. Randolph and dos Santos Ferreira, Ricardo",
    title = "Fast Analysis of Upstream Features on Spatial Networks {(GIS Cup)}",
    note = "Winner (1st place)",
    booktitle = "Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems",
    series = "SIGSPATIAL '18",
    year = "2018",
    isbn = "978-1-4503-5889-7",
    location = "Seattle, Washington",
    pages = "622--625",
    numpages = "4",
    acmid = "3276474",
    publisher = "ACM",
    address = "New York, NY, USA",
    keywords = "GISCUP, graph algorithms, parallel programming, spatial networks",
    href = "\bibhrefpt{228-salles-giscup-2018}{228-salles-giscup-2018-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/228-salles-giscup-2018-talk.pdf",
    mykey = "recent salles parallel sallesgiscup2018",
    doi = "https://doi.org/10.1145/3274895.3276474"
}

Abstract

We present a fast linear time algorithm that uses a block-cut tree for identifying upstream features from a set of starting points in a network. Our implementation has been parallelized and it can process a dataset with 32 million features in less than 8 seconds on a 8-core workstation. This problem is the 2018 ACM SIGSPATIAL CUP challenge and presents several applications mainly on the field of utility networks. Our code is freely available for nonprofit research and education at https://github.com/sallesviana/FastUpstream

Full Text

[download]