Range query processing on single and multi GPU environments

•We proposed strategies over a GPU using the indexes LC and SSS-Index to solve range queries on metric spaces.•Based on previous work, we proposed and compared different searching strategies of the LC index for a multi-GPU platform.•We compared our GPU and multi-GPU proposals against previous OpenMP implementations.•We validate our proposals when it is not acceptable to wait for thousands of queries before processing them all in parallel.•We were able to obtain a super linear speedup with our multi-GPU strategies over the single GPU version.

Metric-space similarity search has proven suitable in a number of application domains such as multimedia retrieval and computational biology to name a few. These applications usually work on very large databases that are often indexed to speed-up on-line searches. To achieve efficient throughput, it is essential to exploit the intrinsic parallelism in the respective search query processing algorithms. Many strategies have been proposed in the literature to parallelize these algorithms either on shared or distributed memory multiprocessor systems. Lately, GPUs have been used to implement brute-force parallel search strategies instead of using index data structures. Indexing poses difficulties when it comes to achieve efficient exploitation of GPU resources. In this paper we propose single and multi GPU metric space techniques that efficiently exploit GPU tailored index data structures for parallel similarity search in large databases. The experimental results show that our proposal outperforms previous index-based sequential and OpenMP search strategies.

Graphical abstractGraphical abstract ASSREFigure optionsDownload full-size imageDownload as PowerPoint slide