A bitmap is an efficient array of boolean values. They are commonly used in bitmap indexes. The Java language has a bitmap class: BitSet.

Unfortunately, the Java BitSet class will not scale to large sparse bitmaps—the Sun implementation does not use compression.

I published a new free alternative: JavaEWAH.




  1. I have just downloaded the software. I have just one preliminary question: how are you sure that EWAH is not patented. In other words why do you think that a patent on WAH does not cover EWAH as well.

    Comment by Anonymous — 3/2/2009 @ 12:55

  2. @Anonymous

    My statement is very clear: to my knowledge, there is no patent violation. However, I am a researcher, not a patent lawyer.

    Comment by Daniel Lemire — 3/2/2009 @ 13:30

  3. Hi,

    Great paper, great wok, nothing to add… I’m currently in Dublin, Ireland, it is amazing that I can download your paper and enjoy your work. Thanks a lot!

    Comment by Jaroslaw — 9/2/2009 @ 5:07

  4. Daniel,

    Is there a way to check whether a bit at the given position is set? In the constant time of course, not using the iterator. Thanks in advance.

    Comment by Igor — 27/1/2011 @ 15:42

  5. No. It is a matter of trade-off: if you want fast random access, a different (less aggressive) form of compression is required. Thanks for the question.

    Comment by Daniel Lemire — 27/1/2011 @ 19:42

Sorry, the comment form is closed at this time.

« Blog's main page

Powered by WordPress