推荐sillysaurusx · 2020-08
“It's very readable, too! Consistently faster and smaller compressed bitmaps with Roaring”
推荐这篇 Roaring 论文,认为很易读
Roaring 压缩位图:混合位图、数组与 RLE,更快更小
论文在 Roaring 混合压缩位图的基础上加入游程编码(RLE)压缩段,使其在数据排序后含有长游程时也能压得更小。新的 Roaring 格式结合了未压缩位图、打包数组和 RLE 压缩段。作者称其比 WAH、Concise、EWAH 等传统基于 RLE 的方案快数倍到两个数量级,同时压缩得更好,并讨论了实现中的设计取舍和优化。
有评论者夸它读起来很顺畅;另有人在评价别的压缩位图对比时指出,其中意外地缺少 Roaring。
候选里有两篇直接相关:一篇是向量化整数压缩,另一篇是 Roaring 的最初版本,先读它们再读这篇加入 RLE 容器的扩展版。
向量化整数压缩的解码方案,是 Roaring 利用 SIMD 加速的背景。
读SIMD 友好的位打包思想,以及解码速度上的收益。
Roaring 的最初论文,目标论文是在它的基础上加入 run 容器并做大规模评测。
读两层结构(高 16 位分块)、数组容器与位图容器的切换阈值,以及与 RLE 类方案的对比。
在 Roaring 中加入 run 容器,混合位图、数组与 RLE,并在更多数据集上评测。
读run 容器的设计与何时选用,以及各类压缩位图的体积和速度对比。
“It's very readable, too! Consistently faster and smaller compressed bitmaps with Roaring”
“what is surprisingly missing from their comparison is roaring bitmaps [0]”