Package com.googlecode.javaewah.symmetric

Class ThresholdFuncBitmap

java.lang.Object

com.googlecode.javaewah.symmetric.UpdateableBitmapFunction

com.googlecode.javaewah.symmetric.ThresholdFuncBitmap

public final class ThresholdFuncBitmap
extends UpdateableBitmapFunction

A threshold Boolean function returns true if the number of true values exceed a threshold. It is a symmetric Boolean function. This class implements an algorithm described in the following paper: Owen Kaser and Daniel Lemire, Compressed bitmap indexes: beyond unions and intersections http://arxiv.org/abs/1402.4466 It is not thread safe: you should use one object per thread.

Since:

0.8.0

See Also:

http://en.wikipedia.org/wiki/Symmetric_Boolean_function

Field Summary

Fields

Modifier and Type	Field	Description
private int[]	bufCounters
private long[]	buffers
private int	bufferUsed
private int	min
private static int[]	zeroes64

Fields inherited from class com.googlecode.javaewah.symmetric.UpdateableBitmapFunction

b, hammingWeight, litWeight, litwlist, rw

Constructor Summary

Constructors

Constructor	Description
ThresholdFuncBitmap(int min)	Construction a threshold function with a given threshold

Method Summary

Modifier and Type	Method	Description
private void	andLiterals(BitmapStorage out, int runBegin, int runLength)
void	dispatch(BitmapStorage out, int runBegin, int runEnd)	Writes out the answer.
private void	generalLiterals(int deficit, BitmapStorage out, int runBegin, int runLength)
private void	orLiterals(BitmapStorage out, int runBegin, int runLength)
private long	threshold2buf(int t, long[] buf, int bufUsed)
private static long	threshold3(int t, long[] buffers, int bufUsed)
private long	threshold4(int T, long[] buf, int bufUsed)

Methods inherited from class com.googlecode.javaewah.symmetric.UpdateableBitmapFunction

clearLiteral, fillWithLiterals, getLiterals, getNumberOfLiterals, resize, setLiteral, setOne, setZero

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

min

private final int min

buffers

private long[] buffers

bufferUsed

private int bufferUsed

bufCounters

private final int[] bufCounters

zeroes64

private static final int[] zeroes64

Constructor Detail

ThresholdFuncBitmap

public ThresholdFuncBitmap(int min)

Construction a threshold function with a given threshold

Parameters:

min - threshold

Method Detail

dispatch

public void dispatch(BitmapStorage out,
                     int runBegin,
                     int runEnd)

Description copied from class: UpdateableBitmapFunction

Writes out the answer.

Specified by:

dispatch in class UpdateableBitmapFunction

Parameters:

out - output buffer

runBegin - beginning of the run

runEnd - end of the run

threshold2buf

private long threshold2buf(int t,
                           long[] buf,
                           int bufUsed)

threshold3

private static long threshold3(int t,
                               long[] buffers,
                               int bufUsed)

threshold4

private long threshold4(int T,
                        long[] buf,
                        int bufUsed)

orLiterals

private void orLiterals(BitmapStorage out,
                        int runBegin,
                        int runLength)

andLiterals

private void andLiterals(BitmapStorage out,
                         int runBegin,
                         int runLength)

generalLiterals

private void generalLiterals(int deficit,
                             BitmapStorage out,
                             int runBegin,
                             int runLength)