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 by several important systems:
Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience (to appear) arXiv:1402.6407. (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.5,)</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.
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 C++.
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.