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

Better bitmap performance with Roaring bitmaps

Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin · 2014
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2017-12-12 · 最近 2018-10-06
2不同的人
2活跃月份
2讨论串
161被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Bitmap indexes are commonly used in databases and search engines. By exploiting bit-level parallelism, they can significantly accelerate queries. However, they can use much memory, and thus we might prefer compressed bitmap indexes. Following Oracle's lead, bitmaps are often compressed using run-length encoding (RLE). Building on prior work, we introduce the Roaring compressed bitmap format: it uses packed arrays for compression instead of RLE. We compare it to two high-performance RLE-based bitmap encoding techniques: WAH (Word Aligned Hybrid compression scheme) and Concise (Compressed `n' Composable Integer Set). On synthetic and real data, we find that Roaring bitmaps (1) often compress significantly better (e.g., 2 times) and (2) are faster than the compressed alternatives (up to 900 times faster for intersections). Our results challenge the view that RLE-based bitmap compression is best.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论willglynn · 2017-12

“There are a lot of tools available in the "compressed bitmap" space. When last I needed something like this, I evaluated several approaches and ended up selecting Roaring Bitmaps: https://arxiv.org/abs/1402.6407 http://roaringbitmap.org That application had some particular wins relating to large sparse bitmaps, especially the ability to efficiently per…”

On-the-fly encoding and decoding of bitmaps原评论 ↗
评论kuwze · 2018-10

“Edit: I misspoke. It seems that they did a very thorough comparison with Word Aligned Hybrid compression scheme. I was just searching the PDFs for 'fastbit'. Past discussion of Roaring bitmaps[0]. I find it interesting that there is no real comparison (at least under the publications at the home page[1]) between Roaring bitmaps and FastBit[2] except for…”

Roaring Bitmaps: Implementation of an Optimized Software Library (2018) [pdf]原评论 ↗