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

Author(s)

Gaioso, Roussian ; Guardia, Helio ; Gil-Costa, Veronica ; Senger, Hermes ; IEEE

• Document type: Journal article
• Source: 2019 31ST INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD 2019); v. N/A, p. 8-pg., 2019-01-01.

Abstract

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 size-based partitioning showed higher speedups (18x) but lower recall for retrieved documents, while the docID-based partitioning can retrieve the exact top-k documents with slightly lower speedups (16x). 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. (AU)

• FAPESP's process: 18/00452-2 - Supporting scalablility and efficiency for scientific applications
• Grantee: Hermes Senger
• Support Opportunities: Regular Research Grants
• FAPESP's process: 15/24461-2 - A study of business models for the federation of services supporting e-Science
• Grantee: Francisco Vilar Brasileiro
• Support Opportunities: Research Projects - Thematic Grants