Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

- L. Arge
- G.S. Brodal
- J. Truelsen, Denmark
- C. Tsirogiannis, Denmark

n 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 N−−√ x N−−√ cells. We want to compute for every integer 2 ≤μ≤N−−√ a raster Gμ of [ N−−√/μ ] x [ 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.

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.

Original language | English |
---|---|

Title of host publication | Algorithms – ESA 2013 : 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings |

Number of pages | 12 |

Publisher | Springer VS |

Publication year | 2013 |

Pages | 61-72 |

ISBN (print) | 9783642404498 |

ISBN (Electronic) | 978-3-642-40450-4 |

DOIs | |

Publication status | Published - 2013 |

Event | European Symposium on Algorithms - Sophia Antipolis, France Duration: 2 Sep 2013 → 4 Sep 2013 Conference number: 21 |

Conference | European Symposium on Algorithms |
---|---|

Nummer | 21 |

Land | France |

By | Sophia Antipolis |

Periode | 02/09/2013 → 04/09/2013 |

Series | Lecture Notes in Computer Science |
---|---|

Volume | 8125 |

ISSN | 0302-9743 |

See relations at Aarhus University Citationformats

No data available

ID: 166871877