按年被提到
20162020 · 1 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:1603.06549 · cs.DB

Consistently faster and smaller compressed bitmaps with Roaring

更快更小的压缩位图:Roaring
Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser · 2016

Roaring 压缩位图:混合位图、数组与 RLE,更快更小

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 3 人首次 2020-08-06 · 最近 2025-01-23
3不同的人
3活跃月份
3讨论串
56被引(OpenAlex)

论文在 Roaring 混合压缩位图的基础上加入游程编码(RLE)压缩段,使其在数据排序后含有长游程时也能压得更小。新的 Roaring 格式结合了未压缩位图、打包数组和 RLE 压缩段。作者称其比 WAH、Concise、EWAH 等传统基于 RLE 的方案快数倍到两个数量级,同时压缩得更好,并讨论了实现中的设计取舍和优化。

HN 为什么提它

有评论者夸它读起来很顺畅;另有人在评价别的压缩位图对比时指出,其中意外地缺少 Roaring。

方法难度 3 / 5约 50 分钟经得起时间
读之前最好知道
1位图索引(bitmap index)
2游程编码(run-length encoding)
3CPU 缓存与 SIMD 基础
4数据库与搜索引擎的倒排索引

学习路径

读这篇之前,按顺序读书架上的 2 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

候选里有两篇直接相关:一篇是向量化整数压缩,另一篇是 Roaring 的最初版本,先读它们再读这篇加入 RLE 容器的扩展版。

  1. 1
    Decoding billions of integers per second through vectorization通过向量化每秒解码数十亿整数 · 2012

    向量化整数压缩的解码方案,是 Roaring 利用 SIMD 加速的背景。

    读SIMD 友好的位打包思想,以及解码速度上的收益。

  2. 2

    Roaring 的最初论文,目标论文是在它的基础上加入 run 容器并做大规模评测。

    读两层结构(高 16 位分块)、数组容器与位图容器的切换阈值,以及与 RLE 类方案的对比。

  3. 3
    Consistently faster and smaller compressed bitmaps with Roaring更快更小的压缩位图:Roaring · 2016 · 就是这篇

    在 Roaring 中加入 run 容器,混合位图、数组与 RLE,并在更多数据集上评测。

    读run 容器的设计与何时选用,以及各类压缩位图的体积和速度对比。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐sillysaurusx · 2020-08

“It's very readable, too! Consistently faster and smaller compressed bitmaps with Roaring”

推荐这篇 Roaring 论文,认为很易读
Simdjson: Parsing gigabytes of JSON per second原评论 ↗
引用wizzard0 · 2025-01

“what is surprisingly missing from their comparison is roaring bitmaps [0]”

指出对比里意外漏掉了 Roaring bitmaps
Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search原评论 ↗
被提交为 story · 1 次