Parallel Strategies for the Execution of Top-k Queries with MaxScore on GPUs

• Roussian Gaioso UFSCar
• Hélio Crestana Guardia UFSCar
• Veronica Gil-Costa CONICET / UNSL
• Hermes Senger UFSCar

Resumo

MaxScore and its variations are efficient DAAT query evaluation methods which use dynamic pruning based on the potential relevance of documents, to provide fast and precise results. These are essential characteristics for large scale search engines. In an attempt to circumvent the inherent sequential nature of DAAT strategies, we applied two parallel strategies to implement new variations of MaxScore to execute on GPUs. The first strategy splits the posting lists based on their size to share the work among thread blocks and SMs of a GPU, while the second strategy partitions the posting lists based on the range of document IDs (docIDs). In order to improve the pruning efficiency of the parallel algorithms, we also evaluated three different strategies for sharing the threshold among the processing elements. Experiments were carried out under different sizes of the postings list, and results demonstrate the viability of both strategies and their GPU-based implementations. The sizebased partitioning showed higher speedups (18×) but lower recall for retrieved documents, while the docID-based partitioning can retrieve the exact top-k documents with slightly lower speedups (16×). Threshold sharing demonstrated significant performance gains for long postings lists. As novelty and contribution, to the best of our knowledge, this is the first parallelization of MaxScore for GPUs. Results show that our strategies are suitable for the parallelization of a class of DAAT strategies on GPUs.

Palavras-chave: Partitioning algorithms, Graphics processing units, Upper bound, Instruction sets, Indexes, Query processing, GPUs, MaxScore, top-k query processing