GPU-accelerated decoding of integer lists

Antonio Mallia, Michał Siedlaczek, Torsten Suel, Mohamed Zahran

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

An inverted index is the basic data structure used in most current large-scale information retrieval systems. It can be modeled as a collection of sorted sequences of integers. Many compression techniques for inverted indexes have been studied in the past, with some of them reaching tremendous decompression speeds through the use of SIMD instructions available on modern CPUs. While there has been some work on query processing algorithms for Graphics Processing Units (GPUs), little of it has focused on how to efficiently access compressed index structures, and we see some potential for significant improvements in decompression speed. In this paper, we describe and implement two encoding schemes for index decompression on GPU architectures. Their format and decoding algorithm is adapted from existing CPU-based compression methods to exploit the execution model and memory hierarchy offered by GPUs. We show that our solutions, GPU-BP and GPU-VByte, achieve significant speedups over their already carefully optimized CPU counterparts.

Original languageEnglish (US)
Title of host publicationCIKM 2019 - Proceedings of the 28th ACM International Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery
Pages2193-2196
Number of pages4
ISBN (Electronic)9781450369763
DOIs
StatePublished - Nov 3 2019
Event28th ACM International Conference on Information and Knowledge Management, CIKM 2019 - Beijing, China
Duration: Nov 3 2019Nov 7 2019

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Conference

Conference28th ACM International Conference on Information and Knowledge Management, CIKM 2019
CountryChina
CityBeijing
Period11/3/1911/7/19

Keywords

  • Compression
  • Graphics Processing Units (GPUs)
  • Inverted Indexes

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Business, Management and Accounting(all)

Fingerprint Dive into the research topics of 'GPU-accelerated decoding of integer lists'. Together they form a unique fingerprint.

  • Cite this

    Mallia, A., Siedlaczek, M., Suel, T., & Zahran, M. (2019). GPU-accelerated decoding of integer lists. In CIKM 2019 - Proceedings of the 28th ACM International Conference on Information and Knowledge Management (pp. 2193-2196). (International Conference on Information and Knowledge Management, Proceedings). Association for Computing Machinery. https://doi.org/10.1145/3357384.3358067