Approximating Streaming Data with Sketching - Real-Time Analytics - page 430

public class StableBloomSet<E extends Serializable>
extends CountingBloomSet<E> {
int d = 0;
byte C = Byte.MAX_VALUE;
public StableBloomSet(int d,byte C,int m, int[]
seeds)
throws IOException {
super(m,seeds);
this.d = d;
this.C = C;
}
In the theoretical analysis of the algorithm, the d counters are chosen at
random to be decremented. However, this is quite slow and the only
requirement from the analysis is that each counter has a d/m chance of
being decremented at each round. Therefore, the authors choose a single
point k at random and then decrement the subsequent d-1 counters, as
shown in the following code:
private final MersenneTwister random = new
MersenneTwister();
public void decrement() {
int k = random.nextInt();
for(int i=0;i<d;i++)
if(counters[(k+i) % m] > 0) counters[(k+i) % m]--;
}
The update step first calls this decrement function to “age” the filter. It then
updates the filter with the new element by setting the appropriate counts to
their maximum values rather than simply incrementing them:
public boolean add(E arg0) {
decrement();
for(int i=0;i<outputs.length;i++) {
hashes[i].reset();
try {
outputs[i].writeObject(arg0);
outputs[i].flush();
int j = hashes[i].hash() % m;