2020
- W. Randolph Franklin, Salles Viana Gomes de Magalhães, and Wenli Li.
Siting thousands of radio transmitter towers on terrains with billions of points.
2020.
arXiv 2006.16783.
arXiv:2006.16783.
[details] [full text]
Abstract
This paper presents a system that sites (finds optimal locations for) thousands of radio transmitter towers on terrains of up to two billion elevation posts. Applications include cellphone towers, camera systems, or even mitigating environmental visual nuisances. The transmitters and receivers may be situated above the terrain. The system has been parallelized with OpenMP to run on a multicore CPU.
BibTeX
@misc{siting-thousands-2020,
author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes and Li, Wenli",
title = "Siting thousands of radio transmitter towers on terrains with billions of points",
year = "2020",
eprint = "2006.16783",
archivePrefix = "arXiv",
primaryClass = "eess.SP",
note = "arXiv 2006.16783",
href = "\bibhref{237-siting-thousands-2020}",
mykey = "recent salles parallel visibility visviewshedsiting wenlili homepage-selected"
}
2017
- Wenli Li and W. Randolph Franklin.
GPU–accelerated multiple observer siting.
Photogrammetric Engineering & Remote Sensing, 83(6):439–446, June 2017.
doi:https://doi.org/10.14358/PERS.83.6.439.
[details] [full text]
Abstract
We present two fast parallel implementations of the Franklin-Vogt multiple observer siting algorithm, using either OpenMP or CUDA. In this problem, the objective is to site observers on a raster terrain such that the joint area visible by them is maximized. On a terrain with 16385×16385 cells, assuming that observers can see out to a radius-of-interest of 100 cells, finding the approximately 15000 observers that have the greatest coverage takes only 17s in CUDA. That is a factor of 70 speedup from the sequential version. The OpenMP version exhibits a factor of 17 speedup on a 16 core system. Applications for the multiple observer siting problem include radio transmission towers, environmental monitoring sites, and path planning for surveillance drones. The algorithm has four steps: finding the visibility indices of all points, selecting a candidate subset of potential top observers, finding each one's viewshed, and greedily constructing the final solution.
BibTeX
@article{wenli-gpu-siting-2016,
author = "Li, Wenli and Franklin, W. Randolph",
title = "{GPU}--Accelerated Multiple Observer Siting",
journal = "Photogrammetric Engineering \\& Remote Sensing",
year = "2017",
month = "June",
volume = "83",
number = "6",
pages = "439--446",
href = "\bibhref{213-wenli-gpu-siting-2016}",
doi = "https://doi.org/10.14358/PERS.83.6.439",
mykey = "wenlili visviewshedsiting gpusiting parallel"
}
2016
- Maurício Gouvêa Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li.
Using rational numbers and parallel computing to efficiently avoid round-off errors on map simplification.
RBC. Revista Brasileira de Cartografia (Online), 68:1221–1230, 2016.
online at \url http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857.
[details] [full text]
Abstract
This paper presents EPLSimp, an algorithm for map generalization that avoids the creation of topological inconsistencies. EPLSimp is based on Visvalingam-Whyatt's (VW) algorithm on which least “important” points are removed first. Unlike VW's algorithm, when a point is deleted a verification is performed in order to check if this deletion would create topological inconsistencies. This was done by using arbitrary precision rational numbers to completely avoid errors caused by floating-point arithmetic. EPLSimp was carefully implemented to be efficient, although using rational numbers adds an overhead to the computation. This efficiency was achieved by using a uniform grid for indexing the geometric data and parallel computing to speed up the process. As result, simplified models completely free of topologically inconsistent results and round-off errors due to the use of multiple precision rational numbers. In addition, there was a considerable speedup arising from the use of parallel computing.
BibTeX
@article{mauricio-rational-rbc-2016,
author = "Gruppi, Maurício Gouvêa and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
title = "Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification",
journal = "RBC. Revista Brasileira de Cartografia (Online)",
year = "2016",
volume = "68",
pages = "1221-1230",
note = "online at \url{http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857}",
href = "\bibhref{221-mauricio-rational-rbc-2016}",
mykey = "wenlili marcus salles parallel"
}
- Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, Wenli Li, and Maurício Gouvêa Gruppi.
Exact intersection of 3D geometric models.
In Geoinfo 2016, XVII Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, November 2016. Instituto Nacional de Pesquisas Espaciais (Brasil).
[details] [full text] [slides]
Abstract
This paper presents 3D-EPUG-OVERLAY , an exact and parallel algorithm for computing the intersection of 3D triangulated meshes, a problem with applications in several fields such as GIS and CAD. 3D-EPUG-OVERLAY presents several innovations: it employs exact arithmetic and, thus, the computations are completely exact, which avoids topological impossibilities that are often created by floating point arithmetic. Also, it uses a uniform grid to index the geometric data and was designed to be easily parallelizable. Furthermore, we propose the use of Simulation of Simplicity to effectively ensure that all the special cases are properly handled by the algorithm.
BibTeX
@inproceedings{salles-xsect-3d-geoinfo-2016,
author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli and Gruppi, Maurício Gouvêa",
title = "Exact intersection of {3D} geometric models",
booktitle = "Geoinfo 2016, {XVII Brazilian} Symposium on GeoInformatics",
year = "2016",
month = "November",
address = "Campos do Jordão, SP, Brazil",
puburl = "\url{http://www.geoinfo.info/geoinfo\_series.htm}",
publisher = "Instituto Nacional de Pesquisas Espaciais (Brasil)",
mykey = "wenlili marcus salles parallel overlay epug-overlay",
href = "\bibhrefpt{217-salles-xsect-3d-geoinfo-2016}{217-salles-xsect-3d-geoinfo-2016-talk.pdf}",
customlinkslides = "https://wrfranklin.org/p/217-salles-xsect-3d-geoinfo-2016-talk.pdf"
}
- Wenli Li, W. Randolph Franklin, and Salles V. G. de Magalhães.
Computing approximate horizons on a GPU.
In 26th Fall Workshop on Computational Geometry. CUNY Graduate Center, New York, USA, 27-28 Oct 2016.
(extended abstract).
[details] [full text] [slides]
Abstract
We use an O(n log(n)) quadtree-forest algorithm to compute approximate horizons at all points of a DEM, and achieve more than 30 times speedup on a GPU. The result of the algorithm is very close to that of the brute-force algorithm.
BibTeX
@inproceedings{wenli-gpu-horizons-fwcg-2016,
author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G.",
title = "Computing approximate horizons on a {GPU}",
booktitle = "26th Fall Workshop on Computational Geometry",
year = "2016",
month = "27-28 Oct",
address = "{CUNY} Graduate Center, New York, USA",
note = "(extended abstract)",
href = "\bibhrefpt{216-wenli-gpu-horizons-fwcg-2016}{216-wenli-gpu-horizons-fwcg-2016-talk.pdf}",
customlinkslides = "https://wrfranklin.org/p/216-wenli-gpu-horizons-fwcg-2016-talk.pdf",
mykey = "visviewshedsiting wenlili salles"
}
- 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"
}
- Wenli Li, W. Randolph Franklin, Salles V. G. de Magalhães, Marcus V. A. Andrade, and David L. Hedin.
3D segmented ODETLAP compression.
2016.
[details] [full text]
Abstract
We propose a segmented ODETLAP compression algorithm to increase speed, and show that it is usually better in the maximum absolute error than JP3D for 3D datasets. Overdetermined Laplacian partial differential equations (ODETLAP) is a spatial approximation and data compression method. We use the CUSP library to accelerate ODETLAP approximation and the speedup is about 7 times on a GPU over a CPU core. Segmented ODETLAP compression is faster and uses less memory than unsegmented ODETLAP compression. We use the algorithm to compress several atmospheric datasets and an MRI dataset. For evaluation, we also compress the datasets using JPEG 2000 Part 10 JP3D. The results show that the compressed size of the algorithm is about 60\% that of JP3D for the same maximum absolute error.
BibTeX
@misc{wenli-odetlap-2016,
author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Hedin, David L.",
title = "{3D} Segmented {ODETLAP} Compression",
booktitle = "(unpublished)",
year = "2016",
href = "\bibhref{212-wenli-odetlap-2016}",
mykey = "wenlili marcus salles odetlap"
}
- 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"
}
- Wenli Li.
GPU-accelerated terrain processing.
PhD thesis, Rensselaer Polytechnic Institute, 2016.
[details] [full text]
Abstract
This thesis extends Overdetermined Laplacian Partial Differential Equations (ODETLAP) for spatial data approximation and compression and parallelizes multiple observer siting on terrain, using General-Purpose Computing on Graphics Processing Units (GPGPU). Both ODETLAP compression and multiple observer siting use greedy algorithms that are parallelizable within iterations but sequential between iterations. They also demonstrate terrain-related research and applications that benefit from GPU acceleration and showcase the achievable speedups. ODETLAP approximation approximates a spatial dataset from scattered data points on a regular grid by solving an overdetermined system of linear equations that minimizes the absolute Laplacian of the approximation and the value errors of the data points. We show that ODETLAP approximation is a linear operator and is comparable in accuracy with natural neighbor interpolation and the multiquadric-biharmonic method. Using ODETLAP approximation to approximate spatial datasets, ODETLAP compression compresses a dataset as a set of known points and their values and decompresses it as an approximation from the known points. We implement ODETLAP approximation and compression using the CUSP library and the speedup is 8 times on a GPU. We design multiple algorithms to improve the accuracy of ODETLAP compression using a limited number of known points and use them to compress 2D terrain datasets and 3D MRI datasets. The results show that ODETLAP compression is 30% to 50% better in minimizing the maximum absolute error than JPEG 2000 for the terrain datasets and 40% to 60% better than JP3D for the MRI datasets. To further increase speed, we design a segmented ODETLAP compression algorithm and use it to compress larger 3D atmospheric and MRI datasets. The results show that the compressed size of the dataset is 60% that of JP3D for the same maximum absolute error. Multiple observer siting places multiple observer points above a terrain to maximize the total area visible from at least one observer. The algorithm first selects a set of highly visible points as tentative observers, and then iteratively selects observers to maximize the cumulative viewshed. We improve the time and space complexities of the algorithm and parallelize it using CUDA on a GPU and using OpenMP on multi-core CPUs. The speedup is up to 60 times on the GPU and 16 times on two CPUs with 16 cores.
BibTeX
@phdthesis{wenli-phd,
author = "Li, Wenli",
title = "{GPU}-accelerated terrain processing",
school = "Rensselaer Polytechnic Institute",
mykey = "wenlili visviewshedsiting gpusiting parallel theses",
year = "2016"
}
2015
- Mauricio G. Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li.
An efficient and topologically correct map generalization heuristic.
In Proceedings of the 17th International Conference on Enterprise Information Systems (ICEIS), 516–525, paper 236. 2015.
URL: http://www.iceis.org/Abstracts/2015/ICEIS_2015_Abstracts.htm, doi:https://doi.org/10.5220/0005398105160525.
[details] [full text]
Abstract
We present TopoVW, an efficient heuristic for map simplification that deals with a variation of the generalization problem where the idea is to simplify the polylines of a map without changing the topological relationships between these polylines or between the lines and control points. This process is important for maintaining clarity of cartographic data, avoiding situations such as high density of map features, inappropriate intersections. In practice, high density of features may be represented by cities condensed into a small space on the map, inappropriate intersections may produce intersections between roads, rivers, and buildings. TopoVW is a strategy based on the Visvalingam-Whyatt algorithm to create simplified geometries with shapes similar to the original map, preserving topological consistency between features in the output. It uses a point ranking strategy, in which line points are ranked by their effective area, a metric that determines the impact a point will cause to the geometry if removed from the line. Points with inferior effective area are eliminated from the original line. The method was able to process a map with 4 million line points and 10 million control points in less than 2 minutes on a Intel Core 2 Duo processor.
BibTeX
@inproceedings{mauricio-iceis-2015,
author = "Gruppi, Mauricio G. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
title = "An Efficient and Topologically Correct Map Generalization Heuristic",
booktitle = "Proceedings of the 17th International Conference on Enterprise Information Systems (ICEIS)",
year = "2015",
pages = "516-525, paper 236",
doi = "https://doi.org/10.5220/0005398105160525",
isbn = "978-989-758-096-3",
mykey = "wenlili marcus salles",
href = "\bibhref{214-mauricio-iceis-2015}",
url = "http://www.iceis.org/Abstracts/2015/ICEIS\_2015\_Abstracts.htm"
}
- Maurício Gouvêa Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li.
Using rational numbers and parallel computing to efficiently avoid round-off errors on map simplification.
In Geoinfo 2015, XVI Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 29 Nov – 2 Dec 2015.
[details] [full text] [slides]
Abstract
This paper presents EPLSimp, an algorithm for map generalization that avoids the creation of topological inconsistencies. EPLSimp is based on Visvalingam-Whyatt's (VW) algorithm on which least “important” points are removed first. Unlike VW's algorithm, when a point is deleted a verification is performed in order to check if this deletion would create topological inconsistencies. This was done by using arbitrary precision rational numbers to completely avoid errors caused by floating-point arithmetic. EPLSimp was carefully implemented to be efficient, although using rational numbers adds an overhead to the computation. This efficiency was achieved by using a uniform grid for indexing the geometric data and parallel computing to speedup the process.
BibTeX
@inproceedings{mauricio-rational-geoinfo-2015,
author = "Gruppi, Maurício Gouvêa and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
title = "Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification",
booktitle = "Geoinfo 2015, {XVI Brazilian} Symposium on GeoInformatics",
year = "2015",
month = "29 Nov -- 2 Dec",
address = "Campos do Jordão, SP, Brazil",
mykey = "marcus wenlili salles visviewshedsiting",
href = "\bibhrefpt{198-mauricio-rational-geoinfo-2015}{198-mauricio-rational-geoinfo-2015-talk.pdf}",
customlinkslides = "https://wrfranklin.org/p/198-mauricio-rational-geoinfo-2015-talk.pdf"
}
- 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}"
}
- Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li.
Fast exact parallel map overlay using a two-level uniform grid.
In 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial). Bellevue WA USA, 3 Nov 2015.
doi:https://doi.org/10.1145/2835185.2835188.
[details] [full text]
Abstract
We present EPUG-Overlay (Exact Parallel Uniform Grid Overlay), an algorithm to overlay two maps that is fast and parallel, has no roundoff errors, and is freely available. EPUG-Overlay combines several novel aspects. It represents coordinates with rational numbers, thereby ensuring exact computations with no roundoff errors and the ensuing sliver problems and topological impossibilities. For efficiency, EPUG-Overlay performs the map overlay in parallel, thereby utilizing the ubiquitous multicore architecture. Our application goes beyond merely using existing packages, which are inefficient when used in parallel on large problems. Indeed, overlaying two maps with 53,000,000 edges and 730,000 faces took only 322 elapsed seconds (plus 116 seconds for I/O) on a dual 8-core 3.1 GHz Intel Xeon E5-2687 workstation. In contrast, GRASS, executing sequentially and generating roundoff errors, takes 5300 seconds. The overlay operation combines two input maps (planar graphs) containing faces (polygons) separated by polyline edges (chains), into a new map, each of whose faces is the intersection of one face from each input map. Floating point roundoff errors can cause an edge intersection to be missed or the computed intersection point be in a wrong face, leading to a topological inconsistency. Thus, a program might fail to compute a valid output map at all, using any amount of time. This gets worse when the inputs are bigger or have slivers. Heuristics can ameliorate this problem, but only to an extent. By representing each coordinate as a vulgar fraction, with multiprecision numerator and denominator, the computation is exact. EPUG-Overlay also executes various useful subproblems very quickly, such as locating a set of points in a planar graph and finding all the intersections among a large set of small edges. EPUG-Overlay is built on our earlier sequential floating-point algorithm that found the areas of the overlay polygons, without finding the polygons themselves.
BibTeX
@inproceedings{salles-overlay-bigspatial-2015,
author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
title = "Fast exact parallel map overlay using a two-level uniform grid",
booktitle = "4th {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data (BigSpatial)",
year = "2015",
month = "3 Nov",
address = "Bellevue WA USA",
href = "\bibhref{196-salles-overlay-bigspatial-2015}",
doi = "https://doi.org/10.1145/2835185.2835188",
mykey = "wenlili marcus salles overlay parallel"
}
- Wenli Li, W. Randolph Franklin, and Salles V. G. de Magalhães.
Segmented ODETLAP compression.
In 25th Fall Workshop on Computational Geometry. U. Buffalo, New York, USA, 23-24 Oct 2015.
(extended abstract).
[details] [full text]
BibTeX
@inproceedings{wenli-segment-fwcg-2015,
author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G.",
title = "Segmented {ODETLAP} Compression",
booktitle = "25th Fall Workshop on Computational Geometry",
year = "2015",
month = "23-24 Oct",
address = "U. Buffalo, New York, USA",
note = "(extended abstract)",
mykey = "wenlili salles odetlap",
href = "\bibhref{202-wenli-segment-fwcg-2015}"
}
- Salles V. G. de Magalhães, W. Randolph Franklin, Marcus V. A. Andrade, and Wenli Li.
An efficient algorithm for computing the exact overlay of triangulations.
In 25th Fall Workshop on Computational Geometry. U. Buffalo, New York, USA, 23-24 Oct 2015.
(extended abstract).
[details] [full text]
BibTeX
@inproceedings{salles-overlay-fwcg-2015,
author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A. and Li, Wenli",
title = "An efficient algorithm for computing the exact overlay of triangulations",
booktitle = "25th Fall Workshop on Computational Geometry",
year = "2015",
month = "23-24 Oct",
address = "U. Buffalo, New York, USA",
note = "(extended abstract)",
mykey = "wenlili marcus salles overlay",
href = "\bibhref{201-salles-overlay-fwcg-2015}"
}
- W. Randolph Franklin, Marcus Andrade, Wenli Li, and Salles de Magalhães.
Changing problems, databases, and tools in spatial search.
24 Aug 2015.
Talk at U. Zürich, Dept of Geography.
[details] [slides]
BibTeX
@misc{changing-talk-zurich-2015,
author = "Franklin, W. Randolph and Andrade, Marcus and Li, Wenli and de Magalhães, Salles",
title = "Changing problems, databases, and tools in spatial search",
note = "Talk at {U. Zürich}, {Dept} of {Geography}",
month = "24 Aug",
year = "2015",
href = "\bibhreft{204-changing-talk-zurich-2015.pdf}",
customlinkslides = "https://wrfranklin.org/p/204-changing-talk-zurich-2015.pdf",
mykey = "wenlili marcus salles parallel"
}
- Marcus Andrade, Salles de Magalhães, W. Randolph Franklin, and Wenli Li.
Research topics in GIS.
Talk at CCNY, 15 April 2015.
[details] [slides]
BibTeX
@misc{salles-ccny-2015,
author = "Andrade, Marcus and de Magalhães, Salles and Franklin, W. Randolph and Li, Wenli",
title = "Research topics in {GIS}",
howpublished = "Talk at CCNY",
month = "15 April",
year = "2015",
href = "\bibhreft{194-salles-ccny-2015.pdf}",
customlinkslides = "https://wrfranklin.org/p/194-salles-ccny-2015.pdf",
mykey = "marcus wenlili salles parallel"
}
- Wenli Li, W. Randolph Franklin, Marcus Andrade, and Salles de Magalhães.
Research summary: siting and ODETLAP.
Talk at CCNY, 15 April 2015.
[details] [slides]
BibTeX
@misc{wenli-ccny-2015,
author = "Li, Wenli and Franklin, W. Randolph and Andrade, Marcus and de Magalhães, Salles",
title = "Research Summary: Siting and {ODETLAP}",
howpublished = "Talk at CCNY",
month = "15 April",
year = "2015",
mykey = "wenlili marcus salles odetlap",
customlinkslides = "https://wrfranklin.org/p/193-wenli-ccny-2015.pdf",
href = "\bibhreft{193-wenli-ccny-2015.pdf}"
}
2014
- Salles V. G. de Magalhães, W. Randolph Franklin, Wenli Li, and Marcus V. A. Andrade.
Fast map generalization heuristic with a uniform grid.
In 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014). Dallas, Texas, USA, 4–7 Nov 2014.
[details] [full text] [poster] [slides]
BibTeX
@inproceedings{giscup-2014,
author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Li, Wenli and Andrade, Marcus V. A.",
title = "Fast map generalization heuristic with a uniform grid",
booktitle = "22nd {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2014)}",
year = "2014",
month = "4--7 Nov",
address = "Dallas, Texas, USA",
href = "\bibhrefptp{185-acmgis2014-cup}{185-acmgis2014-cup-talk.ppt}{185-acmgis2014-cup-poster.pdf}",
customlinkposter = "https://wrfranklin.org/p/185-acmgis2014-cup-poster.pdf",
customlinkslides = "https://wrfranklin.org/p/185-acmgis2014-cup-talk.ppt",
mykey = "wenlili marcus salles gridgen"
}
- Wenli Li, W. Randolph Franklin, Daniel N. Benedetti, and Salles V. G. de Magalhães.
Parallel multiple observer siting on terrain.
In 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014). Dallas, Texas, USA, 4–7 Nov 2014.
[details] [full text] [poster]
Abstract
This paper presents the optimization and parallelization of the multiple observer siting program, originally developed by Franklin and Vogt. Siting is a compute-intensive application with a large amount of inherent parallelism. The advantage of parallelization is not only a faster program but also the ability to solve bigger problems. We have parallelized the program using two different techniques: OpenMP, using multi-core CPUs, and CUDA, using a general purpose graphics processing unit (GPGPU). Experiment results show that both techniques are very effective. Using the OpenMP program, we are able to site tens of thousands of observers on a 16385 × 16385 terrain in less than 2 minutes, on our workstation with two CPUs and one GPU. The CUDA program achieves the same in about 30 seconds.
BibTeX
@inproceedings{li-acmgis-2014,
author = "Li, Wenli and Franklin, W. Randolph and Benedetti, Daniel N. and de Magalhães, Salles V. G.",
title = "Parallel Multiple Observer Siting on Terrain",
booktitle = "22nd {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2014)}",
year = "2014",
month = "4--7 Nov",
href = "\bibhrefpp{182-acmgis2014-par-siting}{182-acmgis2014-par-siting-poster.pdf}",
address = "Dallas, Texas, USA",
customlinkposter = "https://wrfranklin.org/p/182-acmgis2014-par-siting-poster.pdf",
mykey = "benedetti salles wenlili visviewshedsiting gpusiting parallelsiting parallel"
}
- Guilherme Pena, Salles de Magalhães, Marcus Andrade, Randolph Franklin, Chaulio Ferreira, Wenli Li, and Daniel Benedetti.
An efficient GPU multiple-observer siting method based on sparse-matrix multiplication.
In 3rd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014. Dallas TX USA, 4 Nov 2014.
[details] [full text] [slides]
Abstract
This paper proposes an efficient parallel heuristic for siting observers on raster terrains. More specifically, the goal is to choose the smallest set of points on a terrain such that observers located in these points are able to visualize at least a given percentage of the terrain. This problem is NP-Hard and has several applications such as determining the best places to position (site) communication or monitoring towers on a terrain. Since siting observers is a massive operation, its solution requires a huge amount of processing time even to obtain an approximate solution using a heuristic. This is still more evident when processing high resolution terrains that have become available due to modern data acquiring technologies such as LIDAR and IFSAR. Our new implementation uses dynamic programming and CUDA to accelerate the swap local search heuristic, which was proposed in previous works. Also, to efficiently use the parallel computing resources of GPUs, we adapted some techniques previously developed for sparse-dense matrix multiplication. We compared this new method with previous parallel implementations and the new method is much more efficient than the previous ones. It can process much larger terrains (the older methods are restrictive about terrain size) and it is faster.
BibTeX
@inproceedings{bigspatial-2014,
author = "Pena, Guilherme and de Magalhães, Salles and Andrade, Marcus and Franklin, Randolph and Ferreira, Chaulio and Li, Wenli and Benedetti, Daniel",
title = "An efficient {GPU} multiple-observer siting method based on sparse-matrix multiplication",
booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014",
year = "2014",
month = "4 Nov",
address = "Dallas TX USA",
href = "\bibhrefpt{191-bigspatial-sparse-siting-2014}{191-bigspatial-sparse-siting-2014-talk.pdf}",
customlinkslides = "https://wrfranklin.org/p/191-bigspatial-sparse-siting-2014-talk.pdf",
mykey = "visviewshedsiting benedetti marcus wenlili salles parallel"
}
- Salles V. G. de Magalhães, W. Randolph Franklin, Marcus V. A. Andrade, and Wenli Li.
An efficient map generalization heuristic based on the Visvalingam–Whyatt algorithm.
In 24th Fall Workshop on Computational Geometry. U. Connecticut, Storrs CT, USA, 31 Oct – 1 Nov 2014.
(extended abstract).
[details] [full text] [slides]
BibTeX
@inproceedings{salles-fwcg-2014,
author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A. and Li, Wenli",
title = "An efficient map generalization heuristic based on the {V}isvalingam--{Whyatt} algorithm",
booktitle = "24th Fall Workshop on Computational Geometry",
year = "2014",
month = "31 Oct -- 1 Nov",
address = "U. Connecticut, Storrs CT, USA",
note = "(extended abstract)",
mykey = "wenlili marcus salles",
customlinkslides = "https://wrfranklin.org/p/188-fwcg2014-salles-mapgen-talk.pdf",
href = "\bibhrefpt{188-fwcg2014-salles-mapgen}{188-fwcg2014-salles-mapgen-talk.pdf}"
}
- Wenli Li, W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade.
Restricted bathymetric tracklines interpolation.
In 24th Fall Workshop on Computational Geometry. U. Connecticut, Storrs CT, USA, 31 Oct – 1 Nov 2014.
(extended abstract).
[details] [full text] [slides]
Abstract
In this paper, we propose a method to interpolate a small bathymetry with long and thin sand bars as distinctive features. Underwater terrain, or bathymetry, is measured by a single beam or multibeam echosounder attached under a boat. Measurement points are distributed along the a track of the boat and their positions and values constitute a trackline. Although full coverage is possible in multibeam surveys, tracklines are often sparse and thin, especially in single beam surveys, and it is expected to interpolate the bathymetry from tracklines. There are dozens of existing spatial interpolation methods with their strengths and weaknesses, and some are more widely used than others. One of the methods, overdetermined laplacian partial differentiation equations (ODETLAP), has been successfully used in bathymetry data interpolation and shown to be better than some of the popular methods. However, it is more suited for large-scale bathymetry without significant linear or continuous features.
BibTeX
@inproceedings{li-fwcg-2014,
author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
title = "Restricted Bathymetric Tracklines Interpolation",
booktitle = "24th Fall Workshop on Computational Geometry",
year = "2014",
month = "31 Oct -- 1 Nov",
address = "U. Connecticut, Storrs CT, USA",
note = "(extended abstract)",
mykey = "marcus wenlili salles bathy",
customlinkslides = "https://wrfranklin.org/p/187-fwcg2014-li-bathy-talk.pdf",
href = "\bibhrefpt{187-fwcg2014-li-bathy}{187-fwcg2014-li-bathy-talk.pdf}"
}
2013
- Wenli Li, W. Randolph Franklin, and Daniel Benedetti.
Parallel multiple observer siting on terrain.
In 23rd Fall Workshop on Computational Geometry. City College, New York City, USA, 25–26 Oct 2013.
(extended abstract).
[details] [full text] [slides]
Abstract
Multiple observer siting has much inherent parallelism. We have parallelized the siting package using OpenMP and CUDA. The results show that both methods are effective for parallelizing the program. Although the overall speedups of the two methods are similar, which are about 16, the speedups of the constituent parts of the program are quite different.
BibTeX
@inproceedings{li-fwcg-2013,
author = "Li, Wenli and Franklin, W. Randolph and Benedetti, Daniel",
title = "Parallel Multiple Observer Siting on Terrain",
booktitle = "23rd Fall Workshop on Computational Geometry",
year = "2013",
month = "25--26 Oct",
address = "City College, New York City, USA",
note = "(extended abstract)",
href = "\bibhrefpt{173-fwcg2013-li-parallel-siting}{173-fwcg2013-li-parallel-siting-talk.pdf}",
customlinkslides = "https://wrfranklin.org/p/173-fwcg2013-li-parallel-siting-talk.pdf",
mykey = "benedetti wenlili parallelsiting gpusiting parallel"
}
- Daniel Benedetti, W. Randolph Franklin, and Wenli Li.
CUDA-accelerated ODETLAP: a parallel lossy compression implementation.
In 23rd Fall Workshop on Computational Geometry. City College, New York City, USA, 25–26 Oct 2013.
(extended abstract).
[details] [full text] [slides]
Abstract
We present an implementation of Overdetermined Laplacian Partial Differentiation Equations (ODETLAP) that uses CUDA directly. This lossy compression technique approximates a solution to an overdetermined system of equations in order to reconstruct gridded, correlated data. ODETLAP can be used to compress a dataset or to reconstruct missing data. Parallelism in CUDA provides speed performance improvements over other implementation methods. ODETLAP is inspired by the Laplacian Partial Differential Equation, though it is capable of preserving local extrema. Typical compression techniques are limited to viewing data as being one dimensional. The ODETLAP algorithm instead utilizes the autocorrelation of data in multiple dimensions to perform compression. This allows for improved compression of higher dimensional datasets, as can be found in geographical and environmental data[1, 2]. ODETLAP requires the construction and solution approximation of a sparse over-determined linear system of equations. As a result, the algorithm is quite compute-intensive. Parallelization techniques offer means of improving performance of this algorithm. The CUDA libraries, Thrust and CUSP, will be utilized in this parallel implementation of ODETLAP The Thrust library provides means for construction of the overdetermined system matrix, while the CUSP library contains solvers for such systems.
BibTeX
@inproceedings{benedetti-fwcg-2013,
author = "Benedetti, Daniel and Franklin, W. Randolph and Li, Wenli",
title = "{CUDA}-Accelerated {ODETLAP}: A Parallel Lossy Compression Implementation",
booktitle = "23rd Fall Workshop on Computational Geometry",
year = "2013",
month = "25--26 Oct",
address = "City College, New York City, USA",
note = "(extended abstract)",
href = "\bibhrefpt{172-fwcg2013-benedetti-cuda-odetlap}{172-fwcg2013-benedetti-cuda-odetlap-talk.pdf}",
customlinkslides = "https://wrfranklin.org/p/172-fwcg2013-benedetti-cuda-odetlap-talk.pdf",
mykey = "benedetti wenlili odetlap parallel"
}
No publications match your search. Try another word or clear the search.