Fast generation of multiple resolution instances of raster data sets

L. Arge, H.J. Haverkort, C.P. Tsirogiannis

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
1 Downloads (Pure)

Abstract

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 vN × vN cells we first consider the problem of computing for every 2 = µ = vN a raster Gµ of vN/µ × vN/µ 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 T(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, respectively. 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 T(U log N) 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 (ACMGIS, Redondo Beach CA, USA, November 6-9, 2012)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages52-60
ISBN (Print)978-1-4503-1691-0
DOIs
Publication statusPublished - 2012
Event20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2012) - Redondo Beach, United States
Duration: 6 Nov 20129 Nov 2012
Conference number: 20
http://acmgis2012.cs.umd.edu/

Conference

Conference20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2012)
Abbreviated titleACM SIGSPATIAL GIS 2012)
CountryUnited States
CityRedondo Beach
Period6/11/129/11/12
Internet address

Fingerprint

Data storage equipment
Data transfer
Geographic information systems

Cite this

Arge, L., Haverkort, H. J., & Tsirogiannis, C. P. (2012). Fast generation of multiple resolution instances of raster data sets. In Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACMGIS, Redondo Beach CA, USA, November 6-9, 2012) (pp. 52-60). New York NY: Association for Computing Machinery, Inc. https://doi.org/10.1145/2424321.2424329
Arge, L. ; Haverkort, H.J. ; Tsirogiannis, C.P. / Fast generation of multiple resolution instances of raster data sets. Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACMGIS, Redondo Beach CA, USA, November 6-9, 2012). New York NY : Association for Computing Machinery, Inc, 2012. pp. 52-60
@inproceedings{575a7422828b4c1894cdaa0377b7d9d1,
title = "Fast generation of multiple resolution instances of raster data sets",
abstract = "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 vN × vN cells we first consider the problem of computing for every 2 = µ = vN a raster Gµ of vN/µ × vN/µ 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 T(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, respectively. 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 T(U log N) 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.",
author = "L. Arge and H.J. Haverkort and C.P. Tsirogiannis",
year = "2012",
doi = "10.1145/2424321.2424329",
language = "English",
isbn = "978-1-4503-1691-0",
pages = "52--60",
booktitle = "Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACMGIS, Redondo Beach CA, USA, November 6-9, 2012)",
publisher = "Association for Computing Machinery, Inc",
address = "United States",

}

Arge, L, Haverkort, HJ & Tsirogiannis, CP 2012, Fast generation of multiple resolution instances of raster data sets. in Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACMGIS, Redondo Beach CA, USA, November 6-9, 2012). Association for Computing Machinery, Inc, New York NY, pp. 52-60, 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2012) , Redondo Beach, United States, 6/11/12. https://doi.org/10.1145/2424321.2424329

Fast generation of multiple resolution instances of raster data sets. / Arge, L.; Haverkort, H.J.; Tsirogiannis, C.P.

Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACMGIS, Redondo Beach CA, USA, November 6-9, 2012). New York NY : Association for Computing Machinery, Inc, 2012. p. 52-60.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Fast generation of multiple resolution instances of raster data sets

AU - Arge, L.

AU - Haverkort, H.J.

AU - Tsirogiannis, C.P.

PY - 2012

Y1 - 2012

N2 - 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 vN × vN cells we first consider the problem of computing for every 2 = µ = vN a raster Gµ of vN/µ × vN/µ 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 T(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, respectively. 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 T(U log N) 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.

AB - 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 vN × vN cells we first consider the problem of computing for every 2 = µ = vN a raster Gµ of vN/µ × vN/µ 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 T(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, respectively. 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 T(U log N) 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.

U2 - 10.1145/2424321.2424329

DO - 10.1145/2424321.2424329

M3 - Conference contribution

SN - 978-1-4503-1691-0

SP - 52

EP - 60

BT - Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACMGIS, Redondo Beach CA, USA, November 6-9, 2012)

PB - Association for Computing Machinery, Inc

CY - New York NY

ER -

Arge L, Haverkort HJ, Tsirogiannis CP. Fast generation of multiple resolution instances of raster data sets. In Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACMGIS, Redondo Beach CA, USA, November 6-9, 2012). New York NY: Association for Computing Machinery, Inc. 2012. p. 52-60 https://doi.org/10.1145/2424321.2424329