Roaring bitmaps

A better compressed bitset

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.

Article

Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, arXiv:1402.6407. (Software for paper) (Data used in the paper)

Java Software

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.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.

This Java library is used by Apache Spark.

Go Software

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

Funding

This work was supported by NSERC grant number 26143.