Fundamental Algorithms

This work presents a new indexing data structure for query processing, called the Bin-Hash index that effectively utilizes the parallel processing power of the Graphics Processing Unit (GPU). Our approach concentrates on reducing both the amount of bandwidth and memory required to evaluate a query. We achieve this goal by integrating two key strategies: we use encoded data tables to help overcome the limitations imposed by limited GPU memory, and a technique known as perfect spatial hashing to accelerate the retrieval of raw data necessary for candidate checks. We support our candidate checks with a flexible dual cache (one for the GPU and one for the CPU) that uses independent replacement polices. To this end, the CPU serves as a host to the GPU, only supplying the raw data needed for candidate checks; all query evaluations are performed on the GPU by executing kernels written in NVIDIA’s data-parallel programming language CUDA. In our timing measurements, our new query processing method can be an order of magnitude faster than current state-of-the-art indexing technologies such as the compressed bitmap index.