Roaring bitmaps: Implementation of an optimized software library
- 15 January 2018
- journal article
- research article
- Published by Wiley in Software: Practice and Experience
- Vol. 48 (4) , 867-895
Abstract
Summary: Compressed bitmap indexes are used in systems such as Git or Oracle to accelerate queries. They represent sets and often support operations such as unions, intersections, differences, and symmetric differences. Several important systems such as Elasticsearch, Apache Spark, Netflix's Atlas, LinkedIn's Pivot, Metamarkets' Druid, Pilosa, Apache Hive, Apache Tez, Microsoft Visual Studio Team Services, and Apache Kylin rely on a specific type of compressed bitmap index called Roaring. We present an optimized software library written in C implementing Roaring bitmaps: CRoaring. It benefits from several algorithms designed for the single‐instruction–multiple‐data instructions available on commodity processors. In particular, we present vectorized algorithms to compute the intersection, union, difference, and symmetric difference between arrays. We benchmark the library against a wide range of competitive alternatives, identifying weaknesses and strengths in our software. Our work is available under a liberal open‐source license.Keywords
All Related Versions
Funding Information
- Natural Sciences and Engineering Research Council of Canada (261437)
This publication has 34 references indexed in Scilit:
- Better bitmap performance with Roaring bitmapsSoftware: Practice and Experience, 2015
- Compressed bitmap indexes: beyond unions and intersectionsSoftware: Practice and Experience, 2014
- Reordering rows for better compressionACM Transactions on Database Systems, 2012
- Fast, Small, Simple Rank/Select on Bitmaps2012
- 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
- Index compression using 64‐bit wordsSoftware: Practice and Experience, 2010
- Sorting improves word-aligned bitmap indexesData & Knowledge Engineering, 2010
- An almost optimal algorithm for unbounded searchingInformation Processing Letters, 1976