public final Class EWAHCompressedBitmap

This implements the patent-free(1) EWAH scheme. Roughly speaking, it is a 64-bit variant of the BBC compression scheme used by Oracle for its bitmap indexes.

The objective of this compression type is to provide some compression, while reducing as much as possible the CPU cycle usage.

Once constructed, the bitmap is essentially immutable (unless you call the "set" or "add" methods). Thus, it can be safely used in multi-threaded programs.

This implementation being 64-bit, it assumes a 64-bit CPU together with a 64-bit Java Virtual Machine. This same code on a 32-bit machine may not be as fast. There is also a 32-bit version of this code in the class javaewah32.EWAHCompressedBitmap32.

Here is a code sample to illustrate usage:

EWAHCompressedBitmap ewahBitmap1 = EWAHCompressedBitmap.bitmapOf(0, 2, 55, 64,
        1 << 30);
EWAHCompressedBitmap ewahBitmap2 = EWAHCompressedBitmap.bitmapOf(1, 3, 64,
        1 << 30);
EWAHCompressedBitmap ewahBitmap3 = EWAHCompressedBitmap
        .bitmapOf(5, 55, 1 << 30);
EWAHCompressedBitmap ewahBitmap4 = EWAHCompressedBitmap
        .bitmapOf(4, 66, 1 << 30);
EWAHCompressedBitmap orbitmap = ewahBitmap1.or(ewahBitmap2);
EWAHCompressedBitmap andbitmap = ewahBitmap1.and(ewahBitmap2);
EWAHCompressedBitmap xorbitmap = ewahBitmap1.xor(ewahBitmap2);
andbitmap = EWAHCompressedBitmap.and(ewahBitmap1, ewahBitmap2, ewahBitmap3,
        ewahBitmap4);
ByteArrayOutputStream bos = new ByteArrayOutputStream();
ObjectOutputStream oo = new ObjectOutputStream(bos);
ewahBitmap1.writeExternal(oo);
oo.close();
ewahBitmap1 = null;
ewahBitmap1 = new EWAHCompressedBitmap();
ByteArrayInputStream bis = new ByteArrayInputStream(bos.toByteArray());
ewahBitmap1.readExternal(new ObjectInputStream(bis));
EWAHCompressedBitmap threshold2 = EWAHCompressedBitmap.threshold(2,
        ewahBitmap1, ewahBitmap2, ewahBitmap3, ewahBitmap4);

For more details, see the following papers:

• Daniel Lemire, Owen Kaser, Kamel Aouiche, Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering 69 (1), pages 3-28, 2010. http://arxiv.org/abs/0901.3751
• Owen Kaser and Daniel Lemire, Compressed bitmap indexes: beyond unions and intersections http://arxiv.org/abs/1402.4466

A 32-bit version of the compressed format was described by Wu et al. and named WBC:

• K. Wu, E. J. Otoo, A. Shoshani, H. Nordberg, Notes on design and implementation of compressed bit vectors, Tech. Rep. LBNL/PUB-3161, Lawrence Berkeley National Laboratory, available from http://crd.lbl. gov/~kewu/ps/PUB-3161.html (2001).

Probably, the best prior art is the Oracle bitmap compression scheme (BBC):

• G. Antoshenkov, Byte-Aligned Bitmap Compression, DCC'95, 1995.

1- The authors do not know of any patent infringed by the following implementation. However, similar schemes, like WAH are covered by patents.