Chambi, Samy, Lemire, Daniel, Kaser, Owen et Godin, Robert (2016). Better bitmap performance with Roaring bitmaps. Software: Practice and Experience, 45 (5), 709–719. 10.1002/spe.2325
Fichier(s) associé(s) à ce document :|
PDF
- RoaringBitmap.pdf
Contenu du fichier : Manuscrit soumis (avant évaluation) Licence : Creative Commons CC BY. |
|
| Catégorie de document : | Articles de revues |
|---|---|
| Évaluation par un comité de lecture : | Oui |
| Étape de publication : | Publié |
| Résumé : | 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. |
| Déposant: | Lemire, Daniel |
| Responsable : | Daniel Lemire |
| Dépôt : | 19 mars 2015 20:35 |
| Dernière modification : | 09 avr. 2016 21:46 |
|
RÉVISER |
