Paper & talk awards.

2018

• 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.
  [details] [full text] [slides]
  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

  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"
  }
  

2016

• Salles Viana Gomes de Magalhães, W. Randolph Franklin, Wenli Li, and Marcus Vinicius Alvim Andrade. An efficient map-reduce algorithm for spatio-temporal analysis using spark (GIS Cup). In 5th GIS-focused algorithm competition, GISCup 2016, co-located with ACM SIGSPATIAL GIS. 2016. Winner (2nd place).
  [details] [full text] [slides]
  Abstract

  We present an efficient parallel algorithm for performing spatio-temporal analysis in a Spark cluster. It divides the spatio-temporal cube into partitions and uses these partitions as the elements of the Spark Resilient Distributed Datasets (RDDs). As a result, data presents a better locality and the overheads are smaller than the overheads observed when single cells are used as elements of the RDDs. When used to find hotspots in the NYC Yellowcab data, our algorithm is up to 52 times faster than algorithms using single cells RDDs.

  BibTeX

  @inproceedings{salles-giscup-2016,
      author = "de Magalhães, Salles Viana Gomes and Franklin, W. Randolph and Li, Wenli and Andrade, Marcus Vinicius Alvim",
      title = "An efficient map-reduce algorithm for spatio-temporal analysis using Spark ({GIS Cup})",
      note = "Winner (2nd place)",
      booktitle = "5th {GIS}-focused algorithm competition, {GISCup} 2016, co-located with {ACM SIGSPATIAL GIS}",
      year = "2016",
      href = "\bibhrefpt{215-salles-giscup-2016}{215-salles-giscup-2016-talk.pdf}",
      customlinkslides = "https://wrfranklin.org/p/215-salles-giscup-2016-talk.pdf",
      mykey = "marcus wenlili salles parallel sallesgiscup2016"
  }
  

2016

• Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. PinMesh – Fast and exact 3D point location queries using a uniform grid. Computer & Graphics Journal, special issue on Shape Modeling International 2016, 58:1–11, August 2016. (online 17 May). Awarded a reproducibility stamp, \url http://www.reproducibilitystamp.com/. URL: http://www.sciencedirect.com/science/article/pii/S0097849316300607, doi:https://doi.org/10.1016/j.cag.2016.05.017.
  [details] [full text] [slides]
  Abstract

  This paper presents PinMesh, a very fast algorithm with implementation to preprocess a polyhedral mesh, also known as a multimaterial mesh, in order to perform 3D point location queries. PinMesh combines several innovative components to efficiently handle the largest available meshes. Because of a 2-level uniform grid, the expected preprocessing time is linear in the input size, and the code parallelizes well on a shared memory machine. Querying time is almost independent of the dataset size. PinMesh uses exact arithmetic with rational numbers to prevent roundoff errors, and symbolic perturbation with Simulation of Simplicity (SoS) to handle geometric degeneracies or special cases. PinMesh is intended to be a subroutine in more complex algorithms. It can preprocess a dataset and perform 1 million queries up to 27 times faster than RCT (Relative Closest Triangle), the current fastest algorithm. Preprocessing a sample dataset with 50 million triangles took only 14 elapsed seconds on a 16-core Xeon processor. The mean query time was 0.6 microseconds.

  BibTeX

  @article{salles-pinmesh-smi-2016,
      author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
      title = "{PinMesh} -- {Fast} and exact {3D} point location queries using a uniform grid",
      journal = "{Computer \\& Graphics Journal}, special issue on {Shape Modeling International} 2016",
      year = "2016",
      volume = "58",
      pages = "1--11",
      month = "August",
      doi = "https://doi.org/10.1016/j.cag.2016.05.017",
      url = "http://www.sciencedirect.com/science/article/pii/S0097849316300607",
      href = "\bibhrefpt{209-salles-smi-pinmesh-2016}{209-salles-smi-pinmesh-2016-talk.pptx}",
      note = "(online 17 May). Awarded a reproducibility stamp, \url{http://www.reproducibilitystamp.com/}.",
      customlinkslides = "https://wrfranklin.org/p/209-salles-smi-pinmesh-2016-talk.pptx",
      mykey = "salles marcus wenlili pinmesh parallel sallespinmeshsmi2016"
  }
  

2015

• Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Fast path planning under polygonal obstacle constraints. In 4th GIS-focused algorithm competition, GISCUP 2015, co-located with ACM SIGSPATIAL GIS. Bellevue WA USA, 4 Nov 2015. Winner (2nd place).
  [details] [full text]
  BibTeX

  @inproceedings{salles-giscup-2015,
      author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
      title = "Fast path planning under polygonal obstacle constraints",
      booktitle = "4th {GIS}-focused algorithm competition, {GISCUP} 2015, co-located with {ACM SIGSPATIAL GIS}",
      year = "2015",
      month = "4 Nov",
      address = "Bellevue WA USA",
      note = "Winner (2nd place)",
      mykey = "wenlili marcus salles pathplan sallesgiscup2015 uplan",
      href = "\bibhref{203-salles-giscup-2015}"
  }
  

2014

• Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. A linear time algorithm to compute the drainage network on grid terrains. J. Hydroinformatics, 16(6):1227–1234, 2014. Update of the winner of the Best Paper Award (2nd place) at AGILE 2012. doi:https://doi.org/10.2166/hydro.2013.068.
  [details] [full text]
  BibTeX

  @article{salles-hydroinformatics-2014,
      author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
      title = "A linear time algorithm to compute the drainage network on grid terrains",
      journal = "J. Hydroinformatics",
      year = "2014",
      volume = "16",
      number = "6",
      pages = "1227--1234",
      href = "\bibhref{166-hydroinformatics-maghalaes-rwflood}",
      doi = "https://doi.org/10.2166/hydro.2013.068",
      note = "Update of the winner of the Best Paper Award (2nd place) at AGILE 2012",
      mykey = "marcus salles rwflood hydro sallesagile2012"
  }
  

2012

• Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain. In Jérome Gensel, Didier Josselin, and Danny Vandenbroucke, editors, Bridging the Geographic Information Sciences: International AGILE'2012 Conference, pages 391–407. Springer, Avignon (France), 24–27 April 2012. URL: http://agile2012.imag.fr/.
  [details] [full text] [slides]
  BibTeX

  @incollection{salles-agile-2012,
      author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
      editor = "Gensel, Jérome and Josselin, Didier and Vandenbroucke, Danny",
      title = "A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain",
      booktitle = "Bridging the Geographic Information Sciences: International {AGILE'2012} Conference",
      publisher = "Springer",
      pages = "391--407",
      isbn = "978-3-642-29062-6",
      year = "2012",
      address = "Avignon (France)",
      month = "24--27 April",
      note = "Winner of the Best Paper Award (2nd place)",
      url = "http://agile2012.imag.fr/",
      customlinkslides = "https://wrfranklin.org/p/151-agile2012-rwflood-talk.pdf",
      href = "\bibhrefpt{151-agile2012-rwflood}{151-agile2012-rwflood-talk.pdf}",
      mykey = "salles marcus hydro rwflood sallesagile2012"
  }
  

2013

• Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, W. R. Franklin, and Guilherme C. Pena. A parallel sweep line algorithm for visibility computation. In Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 24–27 Nov 2013. Winner of best paper award, \url http://www.geoinfo.info/geoinfo2013/index.php.
  [details] [full text]
  Abstract

  This paper describes a new parallel raster terrain visibility (or viewshed) algorithm, based on the sweep-line model of [Van Kreveld 1996]. Computing the terrain visible from a given observer is required for many GIS applications, with applications ranging from radio tower siting to aesthetics. Processing the newly available higher resolution terrain data requires faster architectures and algorithms. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. Our algorithm uses the economical and widely available shared memory model with OpenMP. Experimentally, our parallel speedup is almost linear. On 16 parallel processors, our algorithm is up to 12 times faster than the serial implementation.

  BibTeX

  @inproceedings{chaulio-geoinfo-2013,
      author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. R. and Pena, Guilherme C.",
      title = "A Parallel Sweep Line Algorithm for Visibility Computation",
      booktitle = "Geoinfo 2013, {XIV Brazilian} Symposium on GeoInformatics",
      year = "2013",
      month = "24--27 Nov",
      address = "Campos do Jordão, SP, Brazil",
      href = "\bibhref{174-geoinfo2013-chaulio-sweep}",
      note = "Winner of best paper award, \url{http://www.geoinfo.info/geoinfo2013/index.php}",
      mykey = "marcus salles visviewshedsiting parallel chauliogeoinfo2013"
  }
  

2009

• Tsz-Yam Lau, You Li, Zhongyi Xie, and W. Randolph Franklin. Sea floor bathymetry trackline surface fitting without visible artifacts using ODETLAP. In 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2009). Seattle WA USA, 4–6 Nov 2009. Winner of the best fast forward presentation award.
  [details] [full text] [slides] [poster] [video] [award]
  BibTeX

  @inproceedings{lau-acmgis-2009,
      author = "Lau, Tsz-Yam and Li, You and Xie, Zhongyi and Franklin, W. Randolph",
      title = "Sea Floor Bathymetry Trackline Surface Fitting Without Visible Artifacts Using {ODETLAP}",
      booktitle = "17th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM SIGSPATIAL GIS} 2009)",
      year = "2009",
      address = "Seattle WA USA",
      month = "4--6 Nov",
      note = "Winner of the best fast forward presentation award",
      customlinkslides = "https://wrfranklin.org/p/129-acmgis2009-lau-talk.pdf",
      customlinkposter = "https://wrfranklin.org/p/129-acmgis2009-lau-poster.pdf",
      customlinkvideo = "https://wrfranklin.org/p/129-acmgis2009-lau-video.avi",
      customlinkaward = "https://wrfranklin.org/p/129-acmgis2009-lau-ffaward.jpg",
      href = "\bibhrefpttppv{129-acmgis2009-lau}",
      mykey = "xie youli odetlap bathy lauacmgis2009"
  }