Bitsets, also called bitmaps, are commonly used as fast data structures. Unfortunately, they can use too much memory. To compensate, we often use compressed bitmaps.
Roaring bitmaps are compressed bitmaps which tend to outperform conventional compressed bitmaps such as WAH, EWAH or Concise. In some instances, they can be hundreds of times faster and they often offer significantly better compression.
Roaring bitmaps are used in Apache Lucene (as of version 5.0 using an independent implementation), Druid.io (as of version 0.7) and Apache Spark (as of version 1.2).
Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience (to appear) arXiv:1402.6407. (Software for paper) (Data used in the paper)
You can browse our API documentation online. You can download releases from the Maven repository or from GitHub. If your project depends on roaring, you can specify the dependency in the Maven "pom.xml" file:
<dependencies> <dependency> <groupId>org.roaringbitmap</groupId> <artifactId>RoaringBitmap</artifactId> <version>0.4.9</version> </dependency> </dependencies>
where the version tag should refer to the version you need. Code sample:
import org.roaringbitmap.*; //... RoaringBitmap rr = RoaringBitmap.bitmapOf(1,2,3,1000); RoaringBitmap rr2 = new RoaringBitmap(); for(int k = 4000; k<4255;++k) rr2.add(k); RoaringBitmap rror = RoaringBitmap.or(rr, rr2);
You can also work directly with memory-mapped bitmaps using the MutableRoaringBitmap and ImmutableRoaringBitmap classes.
Generally, our compressed bitmap Java software is hosted on GitHub.
This Java library is used by Druid.io and Apache Spark.
Acknowledgement: We are using the YourKit profiler to optimize Roaring.
You can browse our API documentation online. You can download the code from GitHub. As usual, you can grab a copy by typing:
go get github.com/tgruben/roaring
There is a version of Roaring written in Cython.
There is a version of Roaring written in Rust.
This work was supported by NSERC grant number 26143.