Better bitmap performance with Roaring bitmaps

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.

References in corpus (1)

• Compressed bitmap indexes: beyond unions and intersections

Cited by in corpus (13)

• Peregrine: A Pattern-Aware Graph Mining System
• Techniques for Inverted Index Compression
• Faster Population Counts Using AVX2 Instructions
• Consistently faster and smaller compressed bitmaps with Roaring
• Roaring Bitmaps: Implementation of an Optimized Software Library
• Effortless Data Exploration with zenvisage: An Expressive and Interactive Visual Analytics System
• An Approximate Algorithm for Maximum Inner Product Search over Streaming Sparse Vectors
• Scalable Eventually Consistent Counters over Unreliable Networks
• Query-based versus resource-based cache strategies in tag-based browsing systems
• A computational model for analytic column stores
• Efficient Offline Monitoring of Linear Temporal Logic with Bit Vectors
• Prediction of Horizontal Data Partitioning Through Query Execution Cost Estimation
• You Say 'What', I Hear 'Where' and 'Why': (Mis-)Interpreting SQL to Derive Fine-Grained Provenance