A Compact Data Structure for Raster Datasets

Abstract

[Abstract]: This work presents a compact data structure for storing raster coverages. The proposed structure not only reduces the storage footprint of raster data but also enables direct processing in its compressed form without compromising query performance. The proposed structure is based on the binary encoding of the values of the raster variable. Specifically, the bits of the binary encoding of each cell are stored in the corresponding cells of each of the w = ⌈log2 vmax⌉ binary matrices (with 0 or 1), where vmax is the maximum value of the raster variable. These binary matrices are represented using the compact data structure called the ik2-tree, a variant of the k2-tree. Through a series of preliminary experiments, we compare our proposal with the k2-raster data structure, which, according to the literature, is one of the most efficient structures for representing rasters. The results show that our structure requires approximately 20% less storage than k2-raster. Regarding the execution time for window queries, for small windows (less than 1% of the raster area), both structures exhibit similar performance. However, for window sizes exceeding 10%, the proposed method demonstrates approximately twice the processing speed of the k2-raster approach.