Compressed bitmaps in Java

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.

References:

Credit:

  • Glen Newton gave me the idea for this project.

Published by

Daniel Lemire

A computer science professor at the Université du Québec (TELUQ).

7 thoughts on “Compressed bitmaps in Java”

  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.

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

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

  4. What are your thoughts on a Javascript implementation of EWAH?
    I’m curious if the benefits of cache coherency would outweigh the lack of 64-bit integer support and other JS inefficiencies.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax