Better bitmap performance with Roaring bitmaps [r-libre/602]

Chambi, Samy; Lemire, Daniel; Kaser, Owen, & Godin, Robert (2016). Better bitmap performance with Roaring bitmaps. Software: Practice and Experience, 45 (5), 709–719. https://doi.org/10.1002/spe.2325

File(s) available for this item:

PDF - RoaringBitmap.pdf
Content : Submitted Version
License : Creative Commons Attribution.

Download

Item Type:	Journal Articles
Refereed:	Yes
Status:	Published
Abstract:	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.
Depositor:	Lemire, Daniel
Owner / Manager:	Daniel Lemire
Deposited:	19 Mar 2015 20:35
Last Modified:	09 Apr 2016 21:46

Actions (login required)

RÉVISER