Database Reference
In-Depth Information
int
last = Integer.MAX_VALUE;
public
SlidingWindow(
int
n,
int
k,
int
max) {
this
.n = n;
this
.k = k;
this
.max = max;
}
This implementation takes three parameters:
n
is the size of each reservoir
sample;
k
is the interval between the start of each bucket; and
max
is the
number of elements that are considered for each of the buckets before it
expired. If all of these parameters are set to the same value then this is not
so much a sampler as it is a method for bucketing the data.
On each insert, several different things may happen. If more than
k
elements have been added, a new bucket is created. Then, expired buckets
are removed from the active list and placed on a
completed
queue for
further processing by another thread. Finally, the element is added to each
of the active buckets:
public void
add(E object) {
if
(last >=
this
.k) {
last = 0;
live.add(
new
Reservoir<E>(n));
}
while
(live.peek() !=
null
&& live.peek().total() >=
max)
completed.add(live.poll());
for
(Reservoir<E> e : live) e.add(object);
last++;
}
With this method, each individual sample only contains a sample from a
specific time range. These samples can then be individually processed to
produce estimates that change over time.
Exponentially Biased Sampling
Although sliding windows are easy to implement, they can also use quite a
bit of memory. This is particularly true if the size of the samples and the
windows have a lot of overlap. It also introduces an operation that is linear
in the number of live windows.
