Database Reference
In-Depth Information
heap.add(element);
while(heap.size() > k) heap.remove();
}
}
The Heavy Hitter implementation is nearly identical, except that elements
areremovedfromthequeueiftheydonotmeetthefrequencyrequirements.
Thisalsorequiresthemaintenance ofacounterofallelementsseenthusfar.
public class HeavyHitters<E extends Serializable> {
CountMinSketch<E> sketch;
PriorityQueue<E> heap;
double f = 1.0;
int N = 0;
public HeavyHitters(double f,CountMinSketch<E>
sketch) {
this.sketch = sketch;
this.heap = new PriorityQueue<E>(11,
new SketchComparator<E>(sketch));
this.f = f;
}
public void add(E element) {
N++;
sketch.increment(element);
heap.add(element);
while(heap.size() > 0 &&
f <= (double)sketch.get(heap.peek())/
(double)N)
heap.remove();
}
}
An alternative implementation would not trim the queue on each insert.
Instead, that implementation could wait until the queue was queried for
some reason.
