public final class EWAHCompressedBitmap extends Object implements Cloneable, Externalizable, Iterable<Integer>, BitmapStorage, LogicalElement<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.
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
For more 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. http://arxiv.org/abs/0901.3751
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.
,
Serialized FormModifier and Type | Field and Description |
---|---|
static boolean |
usetrailingzeros
optimization option
|
static int |
wordinbits
The Constant wordinbits represents the number of bits in a long.
|
Constructor and Description |
---|
EWAHCompressedBitmap()
Creates an empty bitmap (no bit set to true).
|
EWAHCompressedBitmap(int buffersize)
Sets explicitly the buffer size (in 64-bit words).
|
Modifier and Type | Method and Description |
---|---|
void |
add(long newdata)
Adding words directly to the bitmap (for expert use).
|
void |
add(long newdata,
int bitsthatmatter)
Adding words directly to the bitmap (for expert use).
|
void |
addStreamOfEmptyWords(boolean v,
long number)
For experts: You want to add many zeroes or ones? This is the method you
use.
|
void |
addStreamOfLiteralWords(long[] data,
int start,
int number)
if you have several literal words to copy over, this might be faster.
|
void |
addStreamOfNegatedLiteralWords(long[] data,
int start,
int number)
Same as addStreamOfLiteralWords, but the words are negated.
|
static EWAHCompressedBitmap |
and(EWAHCompressedBitmap... bitmaps)
Returns a new compressed bitmap containing the bitwise AND values of the
provided bitmaps.
|
EWAHCompressedBitmap |
and(EWAHCompressedBitmap a)
Returns a new compressed bitmap containing the bitwise AND values of the
current bitmap with some other bitmap.
|
static int |
andCardinality(EWAHCompressedBitmap... bitmaps)
Returns the cardinality of the result of a bitwise AND of the values of the
provided bitmaps.
|
int |
andCardinality(EWAHCompressedBitmap a)
Returns the cardinality of the result of a bitwise AND of the values of the
current bitmap with some other bitmap.
|
EWAHCompressedBitmap |
andNot(EWAHCompressedBitmap a)
Returns a new compressed bitmap containing the bitwise AND NOT values of
the current bitmap with some other bitmap.
|
int |
andNotCardinality(EWAHCompressedBitmap a)
Returns the cardinality of the result of a bitwise AND NOT of the values of
the current bitmap with some other bitmap.
|
void |
andNotToContainer(EWAHCompressedBitmap a,
BitmapStorage container)
Returns a new compressed bitmap containing the bitwise AND NOT values of
the current bitmap with some other bitmap.
|
void |
andToContainer(EWAHCompressedBitmap a,
BitmapStorage container)
Computes new compressed bitmap containing the bitwise AND values of the
current bitmap with some other bitmap.
|
static void |
andWithContainer(BitmapStorage container,
EWAHCompressedBitmap... bitmaps)
For internal use.
|
static EWAHCompressedBitmap |
bitmapOf(int... setbits)
Return a bitmap with the bit set to true at the given
positions.
|
int |
cardinality()
reports the number of bits set to true.
|
void |
clear()
Clear any set bits and set size in bits back to 0
|
Object |
clone() |
void |
deserialize(DataInput in)
Deserialize.
|
boolean |
equals(Object o)
Check to see whether the two compressed bitmaps contain the same set bits.
|
EWAHIterator |
getEWAHIterator()
Gets an EWAHIterator over the data.
|
List<Integer> |
getPositions()
get the locations of the true values as one vector.
|
int |
hashCode()
Returns a customized hash code (based on Karp-Rabin).
|
boolean |
intersects(EWAHCompressedBitmap a)
Return true if the two EWAHCompressedBitmap have both at least one true bit
in the same position.
|
IntIterator |
intIterator()
Iterator over the set bits (this is what most people will want to use to
browse the content if they want an iterator).
|
Iterator<Integer> |
iterator()
iterate over the positions of the true values.
|
void |
not()
Negate (bitwise) the current bitmap.
|
static EWAHCompressedBitmap |
or(EWAHCompressedBitmap... bitmaps)
Returns a new compressed bitmap containing the bitwise OR values of the
provided bitmaps.
|
EWAHCompressedBitmap |
or(EWAHCompressedBitmap a)
Returns a new compressed bitmap containing the bitwise OR values of the
current bitmap with some other bitmap.
|
static int |
orCardinality(EWAHCompressedBitmap... bitmaps)
Returns the cardinality of the result of a bitwise OR of the values of the
provided bitmaps.
|
int |
orCardinality(EWAHCompressedBitmap a)
Returns the cardinality of the result of a bitwise OR of the values of the
current bitmap with some other bitmap.
|
void |
orToContainer(EWAHCompressedBitmap a,
BitmapStorage container)
Computes the bitwise or between the current bitmap and the bitmap "a".
|
static void |
orWithContainer(BitmapStorage container,
EWAHCompressedBitmap... bitmaps)
For internal use.
|
void |
readExternal(ObjectInput in) |
void |
serialize(DataOutput out)
Serialize.
|
int |
serializedSizeInBytes()
Report the size required to serialize this bitmap
|
boolean |
set(int i)
set the bit at position i to true, the bits must be set in increasing
order.
|
void |
setSizeInBits(int size)
set the size in bits
|
boolean |
setSizeInBits(int size,
boolean defaultvalue)
Change the reported size in bits of the *uncompressed* bitmap represented
by this compressed bitmap.
|
int |
sizeInBits()
Returns the size in bits of the *uncompressed* bitmap represented by this
compressed bitmap.
|
int |
sizeInBytes()
Report the *compressed* size of the bitmap (equivalent to memory usage,
after accounting for some overhead).
|
int[] |
toArray()
Populate an array of (sorted integers) corresponding to the location of the
set bits.
|
String |
toDebugString()
A more detailed string describing the bitmap (useful for debugging).
|
String |
toString()
A string describing the bitmap.
|
void |
writeExternal(ObjectOutput out) |
EWAHCompressedBitmap |
xor(EWAHCompressedBitmap a)
Returns a new compressed bitmap containing the bitwise XOR values of the
current bitmap with some other bitmap.
|
int |
xorCardinality(EWAHCompressedBitmap a)
Returns the cardinality of the result of a bitwise XOR of the values of the
current bitmap with some other bitmap.
|
void |
xorToContainer(EWAHCompressedBitmap a,
BitmapStorage container)
Computes a new compressed bitmap containing the bitwise XOR values of the
current bitmap with some other bitmap.
|
public static final boolean usetrailingzeros
public static final int wordinbits
public EWAHCompressedBitmap()
public EWAHCompressedBitmap(int buffersize)
buffersize
- number of 64-bit words reserved when the object is created)public void add(long newdata)
add
in interface BitmapStorage
newdata
- the wordpublic void add(long newdata, int bitsthatmatter)
newdata
- the wordbitsthatmatter
- the number of significant bits (by default it should be 64)public void addStreamOfLiteralWords(long[] data, int start, int number)
addStreamOfLiteralWords
in interface BitmapStorage
data
- the literal wordsstart
- the starting point in the arraynumber
- the number of literal words to addpublic void addStreamOfEmptyWords(boolean v, long number)
addStreamOfEmptyWords
in interface BitmapStorage
v
- the boolean valuenumber
- the numberpublic void addStreamOfNegatedLiteralWords(long[] data, int start, int number)
addStreamOfNegatedLiteralWords
in interface BitmapStorage
data
- the literal wordsstart
- the starting point in the arraynumber
- the number of literal words to addpublic EWAHCompressedBitmap and(EWAHCompressedBitmap a)
and
in interface LogicalElement<EWAHCompressedBitmap>
a
- the other bitmappublic void andToContainer(EWAHCompressedBitmap a, BitmapStorage container)
a
- the other bitmapcontainer
- where we store the resultpublic int andCardinality(EWAHCompressedBitmap a)
a
- the other bitmappublic EWAHCompressedBitmap andNot(EWAHCompressedBitmap a)
andNot
in interface LogicalElement<EWAHCompressedBitmap>
a
- the other bitmappublic void andNotToContainer(EWAHCompressedBitmap a, BitmapStorage container)
a
- the other bitmappublic int andNotCardinality(EWAHCompressedBitmap a)
a
- the other bitmappublic int cardinality()
public void clear()
public Object clone() throws CloneNotSupportedException
clone
in class Object
CloneNotSupportedException
public void deserialize(DataInput in) throws IOException
in
- the DataInput streamIOException
- Signals that an I/O exception has occurred.public boolean equals(Object o)
equals
in class Object
Object.equals(java.lang.Object)
public EWAHIterator getEWAHIterator()
public List<Integer> getPositions()
public int hashCode()
public boolean intersects(EWAHCompressedBitmap a)
a
- the other bitmappublic IntIterator intIterator()
public Iterator<Integer> iterator()
public void not()
not
in interface LogicalElement<EWAHCompressedBitmap>
public EWAHCompressedBitmap or(EWAHCompressedBitmap a)
or
in interface LogicalElement<EWAHCompressedBitmap>
a
- the other bitmappublic void orToContainer(EWAHCompressedBitmap a, BitmapStorage container)
a
- the other bitmapcontainer
- where we store the resultpublic int orCardinality(EWAHCompressedBitmap a)
a
- the other bitmappublic void readExternal(ObjectInput in) throws IOException
readExternal
in interface Externalizable
IOException
public void serialize(DataOutput out) throws IOException
out
- the DataOutput streamIOException
- Signals that an I/O exception has occurred.public int serializedSizeInBytes()
public boolean set(int i)
i
- the indexIndexOutOfBoundsException
- if i is negative or greater than Integer.MAX_VALUE - 64public void setSizeInBits(int size)
setSizeInBits
in interface BitmapStorage
size
- number of bitspublic boolean setSizeInBits(int size, boolean defaultvalue)
size
- the size in bitsdefaultvalue
- the default boolean valuepublic int sizeInBits()
sizeInBits
in interface LogicalElement<EWAHCompressedBitmap>
public int sizeInBytes()
sizeInBytes
in interface LogicalElement<EWAHCompressedBitmap>
public int[] toArray()
public String toDebugString()
public String toString()
public void writeExternal(ObjectOutput out) throws IOException
writeExternal
in interface Externalizable
IOException
public EWAHCompressedBitmap xor(EWAHCompressedBitmap a)
xor
in interface LogicalElement<EWAHCompressedBitmap>
a
- the other bitmappublic void xorToContainer(EWAHCompressedBitmap a, BitmapStorage container)
a
- the other bitmapcontainer
- where we store the resultpublic int xorCardinality(EWAHCompressedBitmap a)
a
- the other bitmappublic static void andWithContainer(BitmapStorage container, EWAHCompressedBitmap... bitmaps)
container
- where the result is storedbitmaps
- bitmaps to ANDpublic static EWAHCompressedBitmap and(EWAHCompressedBitmap... bitmaps)
bitmaps
- bitmaps to AND togetherpublic static int andCardinality(EWAHCompressedBitmap... bitmaps)
bitmaps
- bitmaps to ANDpublic static EWAHCompressedBitmap bitmapOf(int... setbits)
setbits
- list of set bit positionspublic static void orWithContainer(BitmapStorage container, EWAHCompressedBitmap... bitmaps)
public static EWAHCompressedBitmap or(EWAHCompressedBitmap... bitmaps)
bitmaps
- bitmaps to OR togetherpublic static int orCardinality(EWAHCompressedBitmap... bitmaps)
bitmaps
- bitmaps to ORCopyright © 2016. All rights reserved.