Fast generation of multiple resolution instances of raster data sets

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Lars Arge
  • Herman Haverkort, Department of Computer Science, TU Eindhoven, NetherlandsConstantinos Tsirogiannis, Denmark
In many GIS applications it is important to study the characteristics
of a raster data set at multiple resolutions. Often
this is done by generating several coarser resolution rasters
from a fine resolution raster. In this paper we describe efficient
algorithms for different variants of this problem.
Given a raster G of √N × √N cells we first consider the
problem of computing for every 2 ≤ μ ≤ √N a raster Gμ
of √N/μ × √N/μ cells such that each cell of Gμ stores the
average of the values of μ×μ cells of G. We describe an algorithm
that solves this problem in (N) time when the handled
data fit in the main memory of the computer. We also
provide two algorithms that solve this problem in external
memory, that is when the input raster is larger than the main
memory. The first external algorithm is very easy to implement
and requires O(sort(N)) data block transfers from/to
the external memory, and the second algorithm requires only
O(scan(N)) transfers, where sort(N) and scan(N) are the
number of transfers needed to sort and scan N elements,
We also study a variant of the problem where instead of
the full input raster we handle only a connected subregion of
arbitrary shape. For this variant we describe an algorithm
that runs in (U logN) time in internal memory, where U is
the size of the output. We show how this algorithm can be
adapted to perform efficiently in the external memory using
O(sort(U)) data transfers from the disk.
We have also implemented two of the presented algorithms,
the O(sort(N)) external memory algorithm for full rasters,
and the internal memory algorithm that handles connected
subregions, and we demonstrate their efficiency in practice.
Original languageEnglish
Title of host publicationProceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems : ACM SIGSPATIAL GIS 2012
EditorsIsabel Cruz , Craig Knoblock
Number of pages9
PublisherAssociation for Computing Machinery
Publication year2012
ISBN (print)978-1-4503-1691-0
Publication statusPublished - 2012
EventACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - Redondo Beach, United States
Duration: 6 Nov 20129 Nov 2012
Conference number: 20


ConferenceACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
LandUnited States
ByRedondo Beach

    Research areas

  • I/O-efficient algorithms, Raster processing, Multiscalar analysis

See relations at Aarhus University Citationformats

ID: 52283835