k2-MS: A Compact Data Structure for Raster Datasets

Abstract

[Abstract]: In this work, we present the compact data structure k2-MS for the representation of raster coverages. k2-MS is based on a sequence of binary matrices (each represented by a k2-tree), which correspond to the binary encoding of the thematic variable values of the raster. The properties of the k2-MS data structure allow it to benefit from the processor instructions PDEP and PEXT, significantly reducing the access time to the structure. Through a series of experiments on different datasets, we evaluated the performance of our structure by comparing it with the k2-raster, one of the most competitive structures reported in the literature. On average, when comparing the best configurations of both approaches, k2-MS is 48% faster for Window queries and 43% faster for Window Range queries, while requiring about 63% of the storage space used by the k2-raster.