# An Optimal and Practical Cache-Oblivious Algorithm for Computing Multiresolution Rasters

In * Proc. 21st Annual European Symposium on Algorithms*, volume 8125 of * Lecture Notes in Computer Science*, pages 61-72. Springer Verlag, Berlin, 2013.

## Abstract

In many scientific applications it is required to reconstruct a raster dataset many times,
each time using a different resolution. This leads to the following problem;
let *G* be a raster of \sqrt{*N*} x \sqrt{*N*} cells.
We want to compute for every integer 2 ≤ μ ≤ \sqrt{*N*} a raster *G*_{μ}
of ⌈ \sqrt{*N*}/μ ⌉ x ⌈ \sqrt{*N*}/μ ⌉ cells where each cell of *G*_{μ}
stores the average of the values of μ x μ cells of *G*. Here we consider
the case where *G* is so large that it does not fit in the main memory of the computer.

We present a novel algorithm that solves this problem in *O*(scan(*N*)) data block transfers
from/to the external memory, and in Θ(*N*) CPU operations; here scan(*N*) is the
number of block transfers that are needed to read the entire dataset from the external
memory. Unlike previous results on this problem, our algorithm achieves this optimal
performance without making any assumptions on the size of the main memory of the computer.
Moreover, this algorithm is cache-oblivious; its
performance does not depend on the data block size and the main memory size.

We have implemented the new algorithm and we evaluate its performance
on datasets of various sizes; we show that it clearly outperforms previous approaches
on this problem. In this way, we provide solid evidence that non-trivial
cache-oblivious algorithms can be implemented so that they perform efficiently
in practice.

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 2013. All rights reserved.

**Online version**

esa13raster.pdf (341 Kb)

**DOI**

10.1007/978-3-642-40450-4_6

**BIBT**_{E}X entry

@incollection{esa13raster,
author = "Lars Arge and Gerth St{\o}lting Brodal and Jakob Truelsen and Constantinos Tsirogiannis",
booktitle = "Proc. 21st Annual European Symposium on Algorithms",
doi = "10.1007/978-3-642-40450-4_6",
isbn = "0302-9743",
pages = "61-72",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "An Optimal and Practical Cache-Oblivious Algorithm for Computing Multiresolution Rasters",
volume = "8125",
year = "2013"
}