Better bitmap performance with Roaring bitmaps. (21st April 2015)

• Record Type: Journal Article
• Authors: Chambi, Samy; Lemire, Daniel; Kaser, Owen; Godin, Robert
• Is Part Of: Software, practice & experience. Volume 46:Number 5(2016)
• Page Start: 709
• Page End: 719
• Publication Date: 2015-04-21
• Subjects: performance -- measurement -- index compression -- bitmap index; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2325
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: 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: Word Aligned Hybrid compression scheme and Compressed 'n' Composable Integer Set. On synthetic and real data, we find that Roaring bitmaps (1) often compress significantly better (e.g., 2×) and (2) are faster than the compressed alternatives (up to 900× faster for intersections). Our results challenge the view that RLE‐based bitmap compression is best. Copyright © 2015 John Wiley & Sons, Ltd.