From a Comprehensive Experimental Survey to a Cost-based Selection Strategy for Lightweight Integer Compression Algorithms
Autor: | Patrick Damme, Juliana Hildebrandt, Annett Ungethüm, Wolfgang Lehner, Dirk Habich |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2019 |
Předmět: |
Computer science
Leichte Datenkompression Vektorisierung SIMD Experiment und Analyse Kostenanalyse Auswahl von Kompressionsalgorithmen Selection strategy Clock rate 020207 software engineering Memory bandwidth 02 engineering and technology Comparative evaluation Lightweight data compression vectorization SIMD experiment and analysis cost modeling compression algorithm selection Computer engineering 020204 information systems 0202 electrical engineering electronic engineering information engineering SIMD ddc:004 ddc:510 Implementation Information Systems Coding (social sciences) Data compression |
Popis: | Lightweight integer compression algorithms are frequently applied in in-memory database systems to tackle the growing gap between processor speed and main memory bandwidth. In recent years, the vectorization of basic techniques such as delta coding and null suppression has considerably enlarged the corpus of available algorithms. As a result, today there is a large number of algorithms to choose from, while different algorithms are tailored to different data characteristics. However, a comparative evaluation of these algorithms with different data and hardware characteristics has never been sufficiently conducted in the literature. To close this gap, we conducted an exhaustive experimental survey by evaluating several state-of-the-art lightweight integer compression algorithms as well as cascades of basic techniques. We systematically investigated the influence of data as well as hardware properties on the performance and the compression rates. The evaluated algorithms are based on publicly available implementations as well as our own vectorized reimplementations. We summarize our experimental findings leading to several new insights and to the conclusion that there is no single-best algorithm. Moreover, in this article, we also introduce and evaluate a novel cost model for the selection of a suitable lightweight integer compression algorithm for a given dataset. |
Databáze: | OpenAIRE |
Externí odkaz: |