Database Reference
In-Depth Information
hashes[i].reset();
outputs[i].writeObject(arg0);
outputs[i].flush();
if(counters[hashes[i].hash() % m] == 0) return
false;
} catch(IOException e) { }
}
return true;
}
Finally, the cardinality calculation merely checks to see whether the counter
is positive:
public int size() {
double X = 0.0;
for(int x : counters) if(x > 0) X += 1.0;
return (int) (Math.
log
(1 - (double)X
/(double)counters.length)
/(Math.
log
(1.0 - 1.0
/(double)counters.length)*(double)hashes.length));
}
Stable Bloom Filters
The Stable Bloom Filter addresses the deletion of elements from the Bloom
Filterinthecontextofatimeseries.Asmentionedbriefly,ifaBloomFilteris
allowed to simply acquire elements from a stream of data, it is possible that
theBloomFilterwillsimplysaturateandreport
true
forallsetmembership
queries as well as report a maximum set cardinality.
The Stable Bloom Filter overcomes this by introducing the notion of aging
into the filter itself. The basic structure of the filter uses counters as with the
Counting Bloom Filter. To simplify things, the implementation of the Stable
Bloom Filter extends the Counting Bloom Filter with two extra parameters
d
and
C
. These two parameters define the number of counters to decrement
before each addition and the maximum value of each counter, respectively.
This is used to “age” the filter by ensuring that values that are not
incremented will eventually return to zero, as in the code example below:
