Parallel Acceleration of CPU and GPU Range Queries Over Large Data Sets


Computer and Information Sciences



Document Type



bitmap indices, WAH compression, range queries, GPU




Data management systems commonly use bitmap indices to increase the efficiency of querying scientific data. Bitmaps are usually highly compressible and can be queried directly using fast hardware-supported bitwise logical operations. The processing of bitmap queries is inherently parallel in structure, which suggests they could benefit from concurrent computer systems. In particular, bitmap-range queries offer a highly parallel computational problem, and the hardware features of graphics processing units (GPUs) offer an alluring platform for accelerating their execution. In this paper, we present four GPU algorithms and two CPU-based algorithms for the parallel execution of bitmap-range queries. We show that in 98.8% of our tests, using real and synthetic data, the GPU algorithms greatly outperform the parallel CPU algorithms. For these tests, the GPU algorithms provide up to 54.1 × speedup and an average speedup of 11.5× over the parallel CPU algorithms. In addition to enhancing performance, augmenting traditional bitmap query systems with GPUs to offload bitmap query processing allows the CPU to process other requests.

Published in

Journal of Cloud Computing

Citation/Other Information

Nelson, M., Sorenson, Z., Myre, J.M., Sawin, J., Chiu, D. (2020). Parallel Acceleration of CPU and GPU Range Queries Over Large Data Sets. Journal of Cloud Computing, 9, 1-21. https://doi.org/10.1186/s13677-020-00191-w

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.