Parallel quadtree encoding of large-scale raster geospatial data on multicore CPUs and GPGPUs

Global remote sensing and large-scale environment modeling have generated vast amounts of raster geospatial images. To gain a better understanding of this data, researchers are interested in performing spatial queries over them, and the computation of those queries' results is greatly facilitated by the existence of spatial indices. Additionally, though there have been major advances in computational power, the I/O transfer is becoming the major bottleneck in the overall system performance. One of the solutions to the I/O channel bandwidth issue is to compress data first and then send it over an I/O channel. Therefore, a compression technique that achieves not only indexing but also compression is highly desirable. The performance of geospatial raster data compression and indexing can benefit from high performance technologies such as General Purpose Graphics Processing Units (GPGPUs) that are increasingly becoming affordable. Our purpose in this article is two-fold: we will first present issues relating to compressing geospatial raster data and popular compression techniques. Afterwards, we will present a parallel implementation of the compression of geospatial raster data using a cache-conscious quadtree data structure. Experiments show that our GPGPU implementation is capable of constructing a BQ-Tree encoding for the 16-bit NASA MODIS geospatial raster of up to 950 MB in less than one second with an Nvidia C2050 GPU card. This performance represents a 3x speedup with respect to our best implementation of the same algorithm on multi-core CPUs with 16 threads, and up to a 12x speedup compared with a multi-core implementation (with 16 threads) of the popular Zlib compression library.