From a Comprehensive Experimental Survey to a Cost-based Selection Strategy for Lightweight Integer Compression Algorithms
From a Comprehensive Experimental Survey to a Cost-based Selection Strategy for Lightweight Integer Compression Algorithms
复制标题
从综合实验调查到轻量级整数压缩算法的基于成本的选择策略
DOI：
10.1145/3323991
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Wolfgang Lehner
中科院分区：
文献类型：
--
作者：
Patrick Damme;Annett Ungethüm;Juliana Hildebrandt;Dirk Habich;Wolfgang Lehner
轻量级整数压缩算法经常应用于内存数据库系统，以解决处理器速度和主存带宽之间日益增长的差距。近年来，矢量化的基本技术，如三角洲编码和零抑制已大大扩大了语料库的可用算法。因此，今天有大量的算法可供选择，而不同的算法是针对不同的数据特征量身定制的。然而，这些算法与不同的数据和硬件特性的比较评价从来没有充分进行文献。为了缩小这一差距，我们进行了详尽的实验调查，评估几个国家的最先进的轻量级整数压缩算法，以及级联的基本技术。我们系统地研究了数据以及硬件属性对性能和压缩率的影响。评估的算法是基于公开可用的实现，以及我们自己的矢量化reimplementations。我们总结了我们的实验结果，导致几个新的见解，并得出结论，没有单一的最佳算法。此外，在本文中，我们还介绍和评估了一种新的成本模型，用于为给定数据集选择合适的轻量级整数压缩算法。
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.
登录
查看更多内容
异构计算资源查询处理的自适应工作安排
DOI：
10.14778/3067421.3067423
发表时间：
2017
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
Tomas Karnagel;Dirk Habich;Wolfgang Lehner
通讯作者：
Wolfgang Lehner
字节寻址非易失性存储器的数据结构工程
DOI：
--
发表时间：
2017
期刊：
SIGMOD Conference
影响因子：
--
作者：
Ismail Oukid;Wolfgang Lehner
通讯作者：
Wolfgang Lehner
DOI：
10.1007/978-3-319-31409-9_6
发表时间：
2015
期刊：
影响因子：
--
作者：
Patrick Damme;Dirk Habich;Wolfgang Lehner
通讯作者：
Wolfgang Lehner
压缩数据的直接转换技术：通用方法和应用场景
DOI：
10.1007/978-3-319-23135-8_11
发表时间：
2015
期刊：
影响因子：
--
作者：
Patrick Damme;Dirk Habich;Wolfgang Lehner
通讯作者：
Wolfgang Lehner
一种基于 SIMD 的通用加速压缩算法的方法
DOI：
--
发表时间：
2015
期刊：
TOIS
影响因子：
--
作者：
Wayne Xin Zhao;Xudong Zhang;D. Lemire;Dongdong Shan;Jian;Hongfei Yan;Ji
通讯作者：
Ji