Abstract

We report efficient algorithms to compute the map algebra operations thresholding, sum/multiplication by a scalar, point-wise sum, and zonal sum over raster data stored in main memory on the compact data structure k2-raster. Raster data correspond to numerical data, such as temperature and elevation measures related to spatial objects like cities, countries, among others. In general, spatial data can be very large, and therefore, they can be stored in main memory in Compact data structures, which allow efficient data storage and query the data in their compressed form. According to the literature, the k2-raster is the best compact data structure to handle raster data, and it corresponds to a k2-tree that stores the maximum and minimum values for each internal node. We theoretically show that map algebra operations can be computed efficiently using a k2- raster compact data structure. In fact, most of the map algebra operations have a theoretical expected time equivalent to the time of traversing the structure.