In this work, we present the compact data structure \(k^2\) -MS for the representation of raster coverages. \(k^2\) -MS is based on a sequence of binary matrices (each represented by a \(k^2\) -tree), which correspond to the binary encoding of the thematic variable values of the raster. The properties of the \(k^2\) -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 \(k^2\) -raster, one of the most competitive structures reported in the literature. On average, when comparing the best configurations of both approaches, \(k^2\) -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 \(k^2\) -raster.
