LAUSR

Support for efficient spatial data storage and retrieval have become a vital component in almost all spatial database systems. While GPUs have become a mainstream platform for high-throughput data processing in recent years, exploiting the massively parallel processing power of GPUs is non-trivial. Current approaches that parallelize one query at a time have low work efficiency and cannot make good use of GPU resources. On the other hand, many spatial database applications are busy systems in which a large number of queries arrive simultaneously. In this paper, we present a comprehensive framework named G-PICS for parallel processing of a large number of spatial queries on GPUs. G-PICS encapsulates efficient parallel algorithms for constructing a variety of spatial trees with different space partitioning methods. G-PICS also provides highly optimized programs for processing major spatial query types, and such programs can be accessed via an API that could be further extended to implement user-defined algorithms. While support for dynamic data inputs is missing in existing work, GPICS implements efficient parallel algorithms for bulk updates of data. Furthermore, G-PICS is designed to work in a MultiGPU environment to support datasets beyond the size of a single GPU’s global memory. Empirical evaluation of G-PICS shows significant performance improvement over the state-of-the-art GPU and parallel CPU-based spatial query processing systems. In particular, G-PICS achieves double-digit speedup over such systems in tree construction (up to 53X), and query processing (up to 80X). Moreover, tree update procedure outperforms the tree construction from scratch under different levels of data movement.