Database Reference
In-Depth Information
Implementing Count-Min Ranges
The implementation of a Count-Min sketch that can cover the space of
32-bit integers uses 32 different levels from 0 to 31, each with the same
width and depth:
public class CountMinRange {
ArrayList<CountMinSketch<Integer>> sketches =
new ArrayList<CountMinSketch<Integer>>();
long N = 0;
int min = Integer.
MAX_VALUE
;
int max = Integer.
MIN_VALUE
;
public CountMinRange(int width,int[] seeds)
throws IOException {
for(int i=0;i<32;i++)
sketches.add(
new CountMinSketch<Integer>(width,seeds));
}
The update step adds the count to the appropriate start parameter of each of
the different levels:
public void increment(int value,long n) {
if(value < min) min = value;
if(value > max) max = value;
for(int i=0;i<32;i++) {
sketches.get(i).increment(value/(1 << i),n);
}
N += n;
}
Range calculations are a little bit more complicated. First, the appropriate
set of dyadic intervals is computed and then the appropriate element from
each of the levels is added to the total. Each level contributes at most two
elements to each range query:
public long range(int a,int b) {
long count = 0;
for(DyadicInterval d :
DyadicInterval.
createIntervals
(a, b)) {
