A C++ library implementing column-oriented bitmap indexes.

If you want just the compressed bitmap component, for use in your own database engine, you can download the EWAHBoolArray archive (or grab it from the github page). It is available under the permissive Apache license.

Usage:

	EWAHBoolArray<uword32> bitset1;
	bitset1.set(1);
	bitset1.set(2);
	bitset1.set(1000);
	bitset1.set(1001);
	bitset1.set(1002);
	bitset1.set(1003);
	bitset1.set(1007);
	bitset1.set(1009);
	bitset1.set(100000);
	EWAHBoolArray<uword32> bitset2;
	bitset2.set(1);
	bitset2.set(3);
	bitset2.set(1000);
	bitset2.set(1007);
	bitset2.set(100000);
	EWAHBoolArray<uword32> orbitset;
	EWAHBoolArray<uword32> andbitset;
	bitset1.logicalor(bitset2,orbitset);
	bitset1.logicaland(bitset2,andbitset);	

One can iterate over set bits:

	for(EWAHBoolArray<uword32>::const_iterator i = orbitset.begin(); 
			i!=orbitset.end(); ++i)
        	cout<<*i<<endl;

More info:

• There is a github repository : http://github.com/lemire/EWAHBoolArray.
• If you prefer Java, see the A compressed alternative to the Java BitSet class
• If you prefer C#, see the CSharpEWAH Library
• For more theoretical details, see the following paper: Daniel Lemire, Owen Kaser, Kamel Aouiche, Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering 69 (1), pages 3-28, 2010.
• There are some related slides: All About Bitmap Indexes... And Sorting Them

Optional download:

There is another (large) package which is a complete database engine, available under GPL called lemurbitmap. In its current format, this library indexes flat files to a bitmap-based column store. It can scale up to one hundred million attribute values, and to billions of lines. Support for projection indexes is also available. It should build without a problem on MacOS and Linux. See doc/index.html for the documentation.