“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…”
Better bitmap performance with Roaring bitmaps
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 条,统计用全部提及“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…”