Consistently faster and smaller compressed bitmaps with Roaring
- 14 April 2016
- journal article
- research article
- Published by Wiley in Software: Practice and Experience
- Vol. 46 (11) , 1547-1569
Abstract
Summary: Compressed bitmap indexes are used in databases and search engines. Many bitmap compression techniques have been proposed, almost all relying primarily on run‐length encoding (RLE). However, on unsorted data, we can get superior performance with a hybrid compression technique that uses both uncompressed bitmaps and packed arrays inside a two‐level tree. An instance of this technique, Roaring, has recently been proposed. Due to its good performance, it has been adopted by several production platforms (e.g., Apache Lucene, Apache Spark, Apache Kylin, and Druid). Yet there are cases where run‐length‐encoded bitmaps are smaller than the original Roaring bitmaps—typically when the data are sorted so that the bitmaps contain long compressible runs. To better handle these cases, we build a new Roaring hybrid that combines uncompressed bitmaps, packed arrays, and RLE‐compressed segments. The result is a new Roaring format that compresses better. Overall, our new implementation of Roaring can be several times faster (up to two orders of magnitude) than the implementations of traditional RLE‐based alternatives (WAH, Concise, and EWAH) while compressing better. We review the design choices and optimizations that make these good results possible. Copyright © 2016 John Wiley & Sons, Ltd.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- A survey of bitmap index compression algorithms for Big DataTsinghua Science and Technology, 2015
- Compressed bitmap indexes: beyond unions and intersectionsSoftware: Practice and Experience, 2014
- Decoding billions of integers per second through vectorizationSoftware: Practice and Experience, 2013
- Reordering rows for better compressionACM Transactions on Database Systems, 2012
- Efficient set intersection for inverted indexingACM Transactions on Information Systems, 2010
- NET-FLiProceedings of the VLDB Endowment, 2010
- Concise: Compressed ‘n’ Composable Integer SetInformation Processing Letters, 2010
- Sorting improves word-aligned bitmap indexesData & Knowledge Engineering, 2010
- Breaking the Curse of Cardinality on Bitmap Indexes2008
- An almost optimal algorithm for unbounded searchingInformation Processing Letters, 1976