Title: Efficient computation of map algebra over raster data stored in the k2-acc compact data structure

Abstract

We present efficient algorithms to compute simple and complex map algebra operations over raster data stored in main memory, using the k2-acc compact data structure. Raster data correspond to numerical data that represent attributes of spatial objects, such as temperature, elevation measures or even full maps. Compact data structures allow efficient data storage in the main memory of a computer, and query them in their compressed form, which allows faster answers. A k2-acc is a set of k2-trees (binary compressed maps), one for every distinct numeric value in the raster matrix. We demonstrate that map algebra operations can be computed efficiently using this compact data structure. In fact, some map algebra operations perform over five orders of magnitude faster compared with algorithms working over uncompressed datasets.