Distributed streams algorithms for sliding windows.
This paper presents algorithms for estimating aggregate functions over a "sliding window" of the N most recent data items in one or more streams. Our results include:<ol>For a single stream, we present the first &egr;-approximation scheme for the number of 1's in a sliding window that is optimal in both worst case time and space. We also present the first &egr; for the sum of integers in [0..R] in a sliding window that is optimal in both worst case time and space (assuming R is at most polynomial in N). Both algorithms are deterministic and use only logarithmic memory words.In contrast, we show that an  deterministic algorithm that estimates, to within a small constant relative error, the number of 1's (or the sum of integers) in a sliding window over the union of distributed streams requires &OHgr;(N) space. We present the first randomized (&egr;,&sgr;)-approximation scheme for the number of 1's in a sliding window over the union of distributed streams that uses only logarithmic memory words. We also present the first (&egr;,&sgr;)-approximation scheme for the number of distinct values in a sliding window over distributed streams that uses only logarithmic memory words.</olOur results are obtained using a novel family of synopsis data structures.
INTRODUCTION
There has been a
urry of recent work on designing effective
algorithms for estimating aggregates and statistics
over data streams [1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 14, 15, 16,
17, 18, 19, 25], due to their importance in applications such
as network monitoring, data warehousing, telecommunica-
tions, and sensor networks. This work has focused almost
entirely on the sequential context of a data stream observed
by a single party. Figure 1 depicts an example data stream,
where each data item is either a 0 or a 1.
On the other hand, for many of these applications, there
are multiple data sources, each generating its own stream. In
network monitoring and telecommunications, for example,
each node/person in the network is a potential source for
new streaming data. In a large retail data warehouse, each
retail store produces its own stream of items sold. To model
such scenarios, we previously proposed a distributed streams
model [13], in which there are a number of data streams,
each stream is observed by a single party, and the aggregate
is computed over the union of these streams.
Moreover, in many real world scenarios (e.g., marketing,
tra-c engineering), only the most recent data is important.
For example in telecommunications, call records are generated
continuously by customers, but most processing is done
only on recent call records. To model these scenarios, Datar
et al. [4] recently introduced the sliding windows setting for
data streams, in which aggregates and statistics are computed
over a \sliding window" of the N most recent items
in the data stream.
This paper studies the sliding windows setting in both
the single stream and distributed stream models, improving
upon previous results under both settings. In order to
describe our results, we rst describe the models and the
previous work in more detail.
1.1 Sequential and Distributed Streams
The goal in a (sequential or distributed) algorithm for
data streams is to approximate a function F while minimizing
(1) the total workspace (memory) used by all the parties,
(2) the time taken by each party to process a data item, and
(3) the time to produce an estimate (i.e., the query time).
Many functions on (sequential and distributed) data streams
require linear space to compute exactly, and so attention is
focused on nding either an (; -approximation scheme or
an -approximation scheme, dened as follows.
Definition 1. An (; -approximation scheme for a quantity
X is a randomized procedure that, given any positive
computes an estimate ^
of X that is
position
position 79
1-rank 42 43 44

Figure

1: An example data stream, through bits. The position in the stream (position) and the rank
among the 1-bits (1-rank) are computed as the stream is processed.
within a relative error of  with probability at least 1 -, i.e.,
Pr
is a deterministic procedure that, given any positive  < 1,
computes an estimate whose worst case relative error is at
most .
Algorithms for a Sliding Window over a Single
Stream. Datar et al. [4] presented a number of interesting
results on estimating functions over a sliding window for
a single stream. A fundamental problem they consider is
that of determining the number of 1's in a sliding window,
which they call the Basic Counting problem. In the stream
in

Figure

1, for example, the number of 1's in the current
window of the 39 most recent items is 20. They presented an
-approximation scheme for Basic Counting that uses only
O( 1
log 2 (N)) memory bits of workspace, processes each
data item in O(1) amortized and O(log N) worst case time,
and can produce an estimate over the current window in
time. They also prove a matching lower bound on the
space. They demonstrated the importance of this problem
by using their algorithm as a building block for a number
of other functions, such as the sum of bounded integers and
the Lp norms (in a restricted model).
We improve upon their results by presenting an -approx-
imation scheme for Basic Counting that matches their space
and query time bounds, while improving the per-item processing
time to O(1) worst case time. We also present an
-approximation scheme for the sum of bounded integers in
a sliding window that improves the worst case per-item processing
time from O(log N) to O(1).
Our improved algorithms use a family of small space data
structures, which we call waves. An example wave for Basic
Counting is given in Figure 2, for the data stream in

Figure

1. (The basic shape is suggestive of an ocean wave
about to break.) The x-axis is the 1-rank, and extends to
the right as new 1-bits arrive. As we shall see, as additional
stream bits arrive, the wave retains this basic shape while
\moving" to the right so that the crest of the wave is always
over the largest 1-rank thus far.
Algorithms for Distributed Streams. In the distributed
streams model [13], each party observes only its
own stream, has limited workspace, and communicates with
the other parties only when an estimate is requested. Specif-
ically, to produce an estimate, each party sends a message
to a Referee who computes the estimate. This model reects
the set-up used by commercial network monitoring
products, where the data analysis front-end serves the role
of the Referee. Among the results in [13] were (i) an (; -
approximation scheme for the number of 1's in the union of
distributed streams (i.e., in the bitwise OR of the streams),
using only O( 1
log(1=-) log n) memory bits per party, where
n is the length of the stream, and (ii) an (; -approximation
scheme for the number of distinct values in a collection of
distributed streams, using only O( 1
log(1=-) log R) memory
bits, where the values are in [0::R]. Both algorithms
use coordinated sampling: each stream is sampled at the
same random positions, for a given sampling rate. Each
party stores the positions of (only) the 1-bits in its sample.
When the stored 1-bits exceed the target space bound, the
sampling probability is reduced, so that the sample ts in
smaller space. Sliding windows were not considered.
In this paper, we combine the idea of a wave with coordinated
sampling. We store a wave consisting of many random
samples of the stream. Samples that contain only the
recent items are sampled at a high probability, while those
containing older items are sampled at a lower probability.
We obtain an (; -approximation scheme for the number
of 1's in the position-wise union of distributed streams over
a sliding window. We also obtain an (; -approximation
scheme for the number of distinct values in sliding windows
over both single and distributed streams. Each scheme uses
only logarithmic memory words per party.
The algorithms we propose are for the distributed streams
model in the stored coins setting [13], where all parties share
a string of unbiased and fully independent random bits, but
these bits must be stored prior to observing the streams,
and the space to store these bits must be accounted for in
the workspace bound. Previous works on streaming models
(e.g., [1, 5, 6, 8, 18, 19]) have studied settings with stored
coins. Stored coins dier from private coins (e.g., as studied
in communication complexity [21, 23, 24]) because the same
random string can be stored at all parties.
1.2 Summary of Contributions
The contributions of this paper are as follows.
1. We introduce a family of synopsis data structures called
waves, and demonstrate their utility for data stream
processing in the sliding windows setting.
2. We present the rst -approximation scheme for Basic
Counting over a single stream that is optimal in worst
case space, processing time, and query time. Specif-
ically, for a given accuracy , it matches the space
bound and O(1) query time of Datar et al. [4], while
improving the per-item processing time from O(1) amortized
(O(log N) worst case) to O(1) worst case.
3. We present the rst -approximation scheme for the
sum of integers in [0::R] in a sliding window over a single
stream that is optimal in worst case space (assum-
ing R is at most polynomial in N ), processing time,
by
by 8
by 4
by 2
by 1
44 67 91847284 9199
window

Figure

2: A deterministic wave and an example window query 39). The x-axis shows the 1-ranks, and
on the y-axis, level i is labeled as \by 2 i ".
and query time. Specically, it improves the per-item
processing time of [4] from O(1) amortized (O(log N)
worst case) to O(1) worst case.
4. We show that in contrast to the single stream case,
no deterministic algorithm can estimate the number
of 1's in a sliding window over the union of distributed
streams within a small constant relative error unless it
uses
space.
5. We present the rst randomized (; -approximation
scheme for the number of 1's in a sliding window over
the union of distributed streams that uses only logarithmic
memory words. We use this as a building
block for the rst (; -approximation scheme for the
number of distinct values in a sliding window over distributed
streams that uses only logarithmic memory
words.
The remainder of the paper is organized as follows. Section
presents further comparisons with previous related
work. Section 3 and Section 4 present results using the
deterministic (randomized, resp.) wave synopsis. Finally,
Section 5 shows how the techniques can be used for various
other functions over a sliding window such as distinct values
counting and nth most recent 1.
2. RELATED WORK
In the paper introducing the sliding windows setting [4],
the authors gave an algorithm for the Basic Counting problem
that uses exponential histograms. An exponential histogram
maintains more information about recently
seen items, less about old items, and none at all about items
outside the \window" of the last N items. Specically, the
k0 most recent 1's are assigned to individual buckets, the k1
next most recent 1's are assigned to buckets of size 2, the k2
next most recent 1's are assigned to buckets of size 4, and
so on, until all the 1's within the last N items are assigned
to some bucket. For each bucket, the EH stores only its size
(a power of 2) and the position of the most recent 1 in the
bucket. Each k i (up to the last bucket) is either 1
Upon receiving a new item, the last bucket is discarded if
its position no longer falls within the window. Then, if the
new item is a 1, it is assigned to a new bucket of size 1. If
this makes
then the two least recent buckets of
size 1 are merged to form a bucket of size 2. If k1 is now too
large, the two least recent buckets of size 2 are merged, and
so on, resulting in a cascading of up to log N bucket merges
in the worst case. As we shall see, our approach using waves
avoids this cascading.
Our previous paper [13] formalized the distributed streams
model and presented several (; -approximation schemes
for aggregates over distributed streams. We also compared
the power of the distributed streams model with the previously
studied merged streams model (e.g., [5, 19]), where all
the data streams arrived at the same party, but interleaved
in an arbitrary order.
The algorithm by Flajolet and Martin [7] and its variant
due to Alon, Matias and Szegedy [1] estimate the number
of distinct values in a stream (and also the number of 1's in
a bit stream) up to a constant relative error of  > 1. The
algorithm works in the distributed streams model too, and
can be adapted to sliding windows [4]. There are two results
we know of that extend this algorithm to work for arbitrary
relative error, by Trevisan [25] and by Bar-Yossef et al. [3]. 1
Trevisan's algorithm can be extended to distributed streams
quite easily, but the cost of extending it to sliding windows is
not clear. There are O(log(1=-)) instances of the algorithm,
using dierent hash functions, and each must maintain the
O( 1
smallest distinct hashed values in the sliding window
of N values. Assuming the hashed values are random, maintaining
just the minimum value over a sliding window takes
O(log N) expected time [4]. We do not know how to extend
the algorithm in [3] to sliding windows, and in addition, its
space and time bounds for single streams are worse than ours
(however, their algorithm can be made list e-cient [3]).
We now quickly survey some other recent related work.
Frameworks for studying data synopses were presented in [12],
along with a survey of results. There have been algorithms
for computing many dierent functions over a data stream
observed by a single party, such as maintaining histograms [16],
maintaining signicant transforms of the data that are used
to answer aggregate queries [14], and computing correlated
aggregates [9]. Babcock et al. [2] considered the problem
1 Datar et al. [4] also reported an extension to arbitrary relative
error for a sliding window over a single stream, using
the Trevisan approach [20].
of maintaining a uniform random sample of a specied size
over a sliding window of the most recent elements.
In communication complexity models [22], the parties have
unlimited time and space to process their respective in-
puts. Simultaneous 1-round communication complexity results
can often be related to the distributed streams model.
The lower bounds from 1-round communication complexity
certainly carry over directly.
None of these previous papers use wave-like synopses.
3. DETERMINISTIC WAVES
In this section, we will rst present our new -approxima-
tion scheme for the number of 1's in a sliding window over
a single stream. Then we will present our new -approx-
imation scheme for the sum of bounded integers in a sliding
window over a single stream. Finally, we will consider distributed
streams, for three natural denitions of a sliding
window over such streams. We will show that our small-
space deterministic schemes can improve the performance
for two of the scenarios, but for the third, no deterministic
-approximation scheme can obtain sub-linear space.
3.1 The Basic Wave
We begin by describing the basic wave, and show how it
yields an -approximation scheme for the Basic Counting
problem for any sliding window up to a prespecied maximum
window size N . The basic wave will be somewhat
wasteful in terms of its space bound, processing time, and
query time.
Consider a data stream of bits, and a desired positive < 1.
To simplify the notation, we will assume throughout that 1
is an integer. We maintain two counters: pos, which is the
current length of the stream, and rank, which is the current
number of 1's in the stream (equivalently, the 1-rank of the
most recent 1).
The wave contains the positions of the recent 1's in the
stream, arranged at dierent \levels". The wave has
dlog(2N)e levels. For contains the
positions of the 1= recent 1-bits whose 1-rank is a
multiple of 2 i . 2 Figure 2 depicts the basic wave for the data
stream in Figure 1, for
3 and 48. In the gure,
there are ve levels, with level i labeled as \by
it contains the positions of the recent 1-bits
whose 1-ranks are 0 modulo 2 i . The 1-ranks are given on
the x-axis.
Given this wave, we estimate the number of 1's in a window
of size n  N as follows. Let
are to estimate the number of 1's in stream positions [s; pos].
The steps are:
1. Let p1 be the maximum position stored in the wave that
is less than s, and p2 the minimum position stored in
the wave that is greater than or equal to s. (If no such
as the exact answer.) Let r1
and r2 be the 1-ranks of p1 and p2 respectively.
2. Return ^
and otherwise r := r 1 +r 2For example, given the window query depicted in Figure 2,
we have
To simplify the description, we describe throughout the
steady state of a wave. Initially, there will be fewer than
1-bits and the wave stores all of them.
As
noted earlier, the actual number of 1's in this window is 20,
and indeed ^
Lemma 1. The above estimation procedure returns an estimate
x that is within a relative error of  of the actual
number of 1's in the window.
Proof. Each level i contains (1= (stored with
their positions in the stream) whose 1-ranks are 2 i apart.
Thus, regardless of the current rank, the earliest 1-rank at
level i is at most rank  2 i  . Thus, the dierence between
rank and the earliest 1-rank in level ' 1 is at least
the dierence in 1-ranks is at least as
large as the dierence in positions, it follows that p1 exists.
Let j be the smallest numbered level containing position p1 .
We know that the number of 1's in the window is in [rank
r2 +1; rank r1 ]. For example, it is between [50 32+1; 50
24] in

Figure

2. Thus if r2 we return the exact
answer. So assume By returning the
midpoint of the range, we guarantee that the absolute error
is at most r 2 r 1
. By construction, there is at most a 2 j gap
between r1 and its next larger position r2 . Thus the absolute
error in our estimate is at most 2 j 1 . To bound the relative
error, we will show that all the positions in level j 1 are
contained in the window, and this includes at least 2 j 1
1's.
Let r3 be the earliest 1-rank at level j 1. Position p1 was not
in level j 1, so r1 < r3 . Since r2 is the smallest 1-rank in the
wave larger than r1 , we have r2  r3 . Moreover, as argued
above, r3  rank
. Therefore, the actual number of 1's
in the window is at least rank r2 +1  rank r3
.
Thus the relative error is less than 1
.
Note that the proof readily extends beyond the steady
state case: Any level with fewer than 1
positions will
contain a position less than s, and hence can not serve the
role of level j 1 above.
3.2 Improvements
We now show how to improve the basic wave in order to
obtain an optimal deterministic wave for a sliding window
of size N . Let N 0 be the smallest power of 2 greater than
or equal to 2N . First, we use modulo N 0 counters for pos
and rank, and store the positions in the wave as modulo N 0
numbers, so that each takes only log N 0 bits, regardless of
the length of the stream. Next, we discard or expire any positions
that are more than N from pos, as these will never be
used, and would create ambiguity in the modulo N 0 arith-
metic. We keep track of both the largest 1-rank discarded
(r1) and the smallest 1-rank still in the wave (r2 ), so that
the number of 1's in a sliding window of size N can be
answered in O(1) time. Processing a 0-bit takes constant
time, while processing a 1-bit takes O(log(N)) worst case
time and O(1) amortized time, as a new 1-bit is stored at
each level i such that its 1-rank is a multiple of 2 i . Each of
these improvements is used for the EH synopsis introduced
by Datar et al. [4], to obtain the same bounds.
However, the deterministic wave synopsis is quite dierent
from the EH synopsis, so the steps used are dierent too.
Signicantly, we can decrease the per-item processing time
to O(1) worst case, as follows. Instead of storing a single
position in multiple levels, we will store each position only
at its maximum level, as shown in Figure 3. 3 For levels
3 In the gure, we have not explicitly discarded positions
by
by 8
by 4
by 2
by 1
44 7672

Figure

3: An optimal deterministic wave. The x-axis shows the 1-ranks, and on the y-axis, level i is labeled
as \by 2 i ".
positions, and for level
' 1, we store d 1
+1e positions. (At all levels, we may store
fewer positions, because we discard expired positions.) In
the wave, the positions at each level are stored in a xed
length queue, called a level queue, so that each time a new
position is added for the level, the position at the tail of the
queue is removed (assuming the queue is full). For example,
using a circular buer for each queue, the new head position
simply overwrites the next buer slot. We maintain a doubly
linked list of the positions (of the 1-bits) in the wave in
increasing order. Positions evicted from the tail of a level
queue are spliced out of this list. As each new stream item
arrives, we check the head of this sorted list to see if the
head needs to be expired.
Finally, as observed in [4], the set of positions is a sorted
sequence of numbers between 0 and N 0 , so by storing the
dierence (modulo N 0 ) between consecutive positions instead
of the absolute positions, we can reduce the space
from O( 1
log(N) log N) bits to O( 1
log 2 (N)) bits.

Figure

4 summarizes the steps of the deterministic wave
algorithm. Putting it altogether, we have:
Theorem 1. The algorithm in Figure 4 is an -approx-
imation scheme for the number of 1's in a sliding window of
size N over a data stream, using O( 1
log 2 (N)) bits. Each
stream item is processed in O(1) worst case time. At each
time instant, it can provide an estimate in O(1) time.
Proof. (sketch) The proof of  relative error follows
along the lines of the proof of Lemma 1, because the set
of positions in the improved wave is the same or a superset
of the set of positions in the basic wave. The wave level in
step 3(a) is the position of the least-signicant 1-bit in rank
(numbering from 0). Assuming this is a constant time op-
eration, the time bounds follow from the above discussion. 4
As for the space, because the level queues are updated in
place, the same block of memory can be used throughout,
and hence the linked list pointers are osets into this block
and not full-sized pointers. The space bound follows.
The space bound is optimal because it matches the lower
outside the size in order to show the full
levels. All positions less than pos
and is the largest expired 1-rank.
4 Below, we show how to determine the wave level in constant
time even on a weaker machine model that does not
explicitly support this operation in constant time.
Upon receiving a stream bit b:
1. Increment pos. (Note: All additions and comparisons
are done modulo N 0 , the smallest power of 2 greater
than or equal to 2N .)
2. If the head (p; r) of the linked list L has expired (i.e.,
discard it from L and from (the
tail of) its queue, and store r as the largest 1-rank
discarded.
3. If
(a) Increment rank, and determine the corresponding
wave level j, i.e., the largest j such that rank is a
multiple of 2 j .
(b) If the level j queue is full, then discard the tail of
the queue and splice it out of L.
(c) Add (pos; rank) to the head of the level j queue
and the tail of L.
Answering a query for a sliding window of size N :
1. Let r1 be the largest 1-rank discarded. (If no such r1 ,
x := rank as the exact answer.) Let r2 be the
1-rank at the head of the linked list L. (If L is empty,
as the exact answer.)
2. Return ^
and otherwise r := r 1 +r 2
Figure

4: A deterministic wave algorithm for Basic
Counting over a single stream.
bound by Datar et al. [4] for both randomized and deterministic
algorithms.
Computing the Wave Level on a Weaker Machine
Model. Step 3(a) of Figure 4 requires computing the least-
signicant 1-bit in a given number. On a machine model
that does not explicitly support this operation in constant
time, a naive approach would be to examine each bit of rank
one at a time until the desired position is found. But this
takes (log N) worst case time, because rank has N 0 bits.
Instead, we store the log N 0 wave levels associated with the
sequence in an array (e.g., f0;
This takes only O(log N
log log N) bits. We also store a counter d of log N 0 log log N 0
bits, initially 1. As 1-bits are received, the desired wave
level is the next element in this array. The rst 1-bit after
reaching the end of the array has the property that the last
log log N 0 bits of rank are 0, and the desired wave level is
log log N 0 plus the position of the least signicant 1-bit in
d (numbering from 0). We then increment d and return to
cycling through the array. This correctly computes the wave
level at each step. Moreover, note that while we are cycling
through the array, we have log N 0 steps until we need to
know the least signicant 1-bit in d. Thus by interleaving
(i) the cycling and (ii) the search through the bits of d, we
can determine each of the wave levels in O(1) worst case
time.
Basic Counting for Any Window of Size n  N .
The algorithm in Figure 4 achieves constant worst case query
time for a sliding window of size N . For a sliding window
of any size n  N , this single wave can be used to give
an estimate for the Basic Counting problem that is within
an  relative error, by following the two steps outlined for
the Basic Wave (Section 3.1). However, the query time for
window sizes less than N is O( 1
log(N)) in the worst case,
because we must search through the linked list L in order to
determine p1 and p2 . This matches the query time bound
for the EH algorithm [4].
3.3 Sum of Bounded Integers
The deterministic wave scheme can be extended to handle
the problem of maintaining the sum of the last N items in a
data stream, where each item is an integer in [0::R]. Datar et
al. [4] showed how to extend their EH approach to obtain an
-approximation scheme for this problem, using O( 1
(log N+
log R)) buckets of log N log R) bits each, O(1)
query time, and O( log R
log N ) amortized and O(log N log R)
worst case per-item processing time. (They also presented
a matching asymptotic lower bound on the number of bits,
under certain weak assumptions on the relative sizes of N ,
R, and .) We show how to achieve constant worst case
per-item processing time, while using the same number of
memory words and the same query time. (The number of
bits is O( 1
(log N+log R) 2 ), which is slightly worse than the
EH bound if R is super-polynomial in N .)
Our algorithm is depicted in Figure 5. The sum over
a sliding window can range from 0 to N  R. Let N 0 be
the smallest power of 2 greater than or equal to 2NR. We
maintain two modulo N 0 counters: pos, the current length,
and total, the running sum. There are
levels. The algorithm follows the same general steps as the
algorithm in Figure 4. Instead of storing pairs (p; r), we
store triples (p; v; z) where v is the value for the data item
(not needed before because the value for a stored item was
always 1) and z is the partial sum through this item (the
equivalent of the 1-rank for sums). When answering a query,
we know that the window sum is in [total z2 +v2 ; total z1 ],
and we return the midpoint of this interval.
The key insight in this algorithm is that it su-ces to store
an item (only) at a level j such that 2 j is the largest power
of 2 that divides a number in (total; total Naively, one
would mimic the Basic Counting wave by viewing a value
v as v items of value 1. But this would take O(R) worst
case time to process an item. Datar et al. [4] reduced this to
log R) time by directly computing the EH resulting
after inserting v items of value 1. However, a single item
is stored in up to O(log N log R) EH buckets. In contrast,
Upon receiving a stream value v 2 [0::R]:
1. Increment pos. (Note: All additions and comparisons
are done modulo N 0 .)
2. If the head (p; v 0 ; z) of the linked list L has expired
(i.e., p  pos N ), then discard it from L and from
(the tail of) its queue, and store z as the largest partial
sum discarded.
3. If v > 0 then do:
(a) Determine the largest j such that some number
in (total; total + v] is a multiple of 2 j . Add v to
total.
(b) If the level j queue is full, then discard the tail of
the queue and splice it out of L.
(c) Add (pos; v; total) to the head of the level j queue
and the tail of L.
Answering a query for a sliding window of size N :
1. Let z1 be the largest partial sum discarded from L.
(If no such z1 , return total as the exact answer.)
Let (p; v2 ; z2) be the head of the linked list L. (If L is
empty, return as the exact answer.)
2. Return ^
x := total
Figure

5: A deterministic wave algorithm for the
sum over a sliding window.
we store the item just once, which enables our O(1) time
bound.
The challenge is to quickly compute the wave level in
step 3(a); we show how to do this in O(1) time. First observe
that the desired wave level is the largest position j
(numbering from 0) such that some number y in the interval
has 0's in all positions less than j (and
hence y is a multiple of 2 j ). Second, observe that y 1 and
y dier in bit position j, and if this bit changes from 1 to
0 at any point in [total; total is not the largest.
Thus, j is the position of the most-signicant bit that is 0
in total and 1 in total + v. Accordingly, let f be the bitwise
complement of total, and let
the bitwise AND of f and g. Then the desired wave level is
the position of the most-signicant 1-bit in h, i.e., blog hc. 5
Putting it altogether, we have:
Theorem 2. The algorithm in Figure 5 is an -approx-
imation scheme for the sum of the last N items in a data
stream, where each item is an integer in [0::R]. It uses
O( 1
(log N log R)) memory words, where each memory
word is O(log N log R) bits (i.e., su-ciently large to hold
an item or a window size). Each item is processed in O(1)
worst case time. At each time instant, it can provide an
5 On a weaker machine model that does not support this
operation on h in constant time, we can use binary search
to nd the desired position in O(log(log N log R)) time,
as follows. Let w be the word size, and B be a bit mask
comprising of w
1's followed by w
0's. We begin by checking
zero. If so, we left shift B by wpositions
and recurse. Otherwise, we right shift B by wpositions and
recurse.
estimate in O(1) time.
Proof. (sketch) For the purposes of analyzing the approximation
error, we reduce the wave to an equivalent basic
wave for the Basic Counting problem, as follows. For each
triple (p; v; z) in the sums wave, we have a pair (p; z 0 ) in the
basic wave for each z stored in all levels l
such that z 0 is a multiple of 2 l . Also add the pair (p1 ; z1)
where z1 is the largest partial sum discarded by the sums
wave algorithm, to all levels l 0 such that z 0 is a multiple of
. Next, for each level, discard all but the most recent + 1 at the level. Let
the minimum level containing p1 . Adapting the argument
in the proof of Lemma 1, it can be shown that (1) regardless
of the current rank, the earliest 1-rank at level i is at most
there is at most a 2 j gap between r1 and
its next larger position r2 , and (3) all the positions in level
are contained in the window.
We know that the window sum is in [total z2 +v2 ; total
z1 ], and since we take the midpoint, the absolute error of
x is at most z 2 v 2 z 1
. The gap between z2 v2 and z1 is
at most the gap between r1 and r2 in the basic wave. Thus
by (2) above, the absolute error is at most 2 j 1 . Moreover,
by (1) and (3) above, the actual window sum is at least
. Thus the relative error is less than 1
.
The space and time bounds are immediate, given the
above discussion of how to perform step 3(a) in constant
time.
3.4 Distributed Streams
We consider three natural denitions for a sliding window
over a collection of t  2 distributed streams, as illustrated
for the Basic Counting problem:
1. We seek the total number of 1's in the last N items in
each of the t streams (t  N items in total).
2. A single logical stream has been split arbitrarily among
the parties. Each party receives items that include a
sequence number in the logical stream, and we seek the
total number of 1's in the last N items in the logical
stream.
3. We seek the total number of 1's in the last N items in
the position-wise union (logical OR) of the t streams.
The deterministic wave can be used to answer sliding windows
queries over a collection of distributed streams, for
both the rst two scenarios. For the rst scenario, we apply
the single stream algorithm to each stream. To answer a
query, each party sends its count to the Referee, who simply
sums the answers. Because each individual count is within
relative error, so is the total. The second scenario can
similarly be reduced to the single stream problem. The only
issue is that each party knows only the latest sequence number
in its stream, not the overall latest, so some waves may
contain expired positions. Thus to answer a query, each
party sends its wave to the Referee, who computes the maximum
sequence number over all the parties and then uses
each wave to obtain an estimate over the resulting window,
and sums the result. Because each individual estimate is
within an  relative error (recall the discussion at the end of
Section 3.2), so is the total. By improving the single stream
performance over the previous work, we have improved the
distributed streams performance for these two scenarios.
However, the third scenario is more problematic. Denote
as the Union Counting problem the problem of counting the
number of 1's in the position-wise union of t distributed data
streams. (If each stream represents the characteristic vector
for a set, then this is the size of the union of these sets.) We
present next a linear space lower bound for deterministic
algorithms for this problem, before considering randomized
algorithms in Section 4.
A Lower Bound for Deterministic Algorithms. We
show the following lower bound on any deterministic algorithm
for the Union Counting problem that guarantees a
small constant relative error.
Theorem 3. Any deterministic algorithm that guarantees
a constant relative error   1for the Union Counting
problem requires
n) space for n-bit streams, even for
parties (and no sliding window).
Proof. The proof is by contradiction. Suppose that an
algorithm existed for approximating Union Counting within
a relative error of 1using space less than n, where
. (We have not attempted to maximize the constants
or .)
Let A and B be the two parties, where A sees the data
stream X and B sees the data stream Y . X and Y are of
length n (n even), and a query request occurs only after both
streams have been observed. Suppose that both X and Y
have exactly n
ones and zeroes. Note that for this restricted
scenario, the exact answer for the Union Counting problem
is n
where H(X;Y ) is the Hamming distance between X and Y .
For each possible message m from A to the Referee C, let
Sm denote the set of all inputs to A for which A sends m
to C. Since A's workspace is only n bits, the number of
distinct messages that A could send to C is 2 n . The number
of possible inputs for A is ( n
Using the pigeonhole
principle, we conclude that there exists a message m that A
sends to C such that
Because the relative error is at most  and the exact answer
is at most n, the absolute error of any estimate produced
by the algorithm is at most n. We claim that no
two inputs in Sm can be at a Hamming distance greater
than 4n. The proof is by contradiction. Suppose there are
two inputs X1 and X2 in Sm such that H(X1 ; X2 ) > 4n.
Consider two runs of the algorithm: in the rst,
and in the second, In
both runs, the Referee C gets the same pair of messages,
and so it outputs the same estimate z. Because the absolute
error in both cases is at most n, we have by equation
(1) that z  n
z  n+ 1
For a given n-bit input t with exactly n
2 1's, the number of
n-bit inputs with exactly n1's at a Hamming distance of k
from t (k an even number) is ( n=2
combinations of kout of n0's in t
ipped to 1's and kout of n1's in t
ipped
to 0's. (There are no such inputs at odd distances.) Thus
the number of such inputs at Hamming distance at most k
is
4 , is at most (1
By the above claim, for all messages m that A sends to C,
we have:
By choosing  = 1in equation (2), we have that
By choosing suitably large, it follows from
equation (3) that
4n
We obtain the contradiction, which completes the proof.
Sum of Bounded Integers. For the sum of bounded
integers problem, scenarios 1 and 2 are straightforward applications
of the single stream algorithm. For scenario 3, if
\union" means to take the position-wise sum, the problem
reduces to the rst scenario. If \union" means to take the
position-wise maximum, then the lower bound applies, as
the number of 1's in the union is a special case of the sum
of the position-wise maximum.
The linear space lower bound for deterministic algorithms
in Theorem 3 is the motivation for considering the randomized
waves introduced in the next section.
4. RANDOMIZED WAVES
Similar to the deterministic wave, the randomized wave
contains the positions of the recent 1's in the data stream,
stored at dierent levels. Each level i contains the most
recently selected positions of the 1-bits, where a position is
selected into level i with probability 2 i . Thus the main
dierence between the deterministic and randomized waves
is that for each level i, the deterministic wave selects 1 out
of every 2 i 1-bits at regular intervals, whereas a randomized
wave selects an expected 1 out of every 2 i 1-bits at random
intervals. Also, the randomize wave retains more positions
per level.
4.1 The Basic Randomized Wave
We begin by describing the basic randomized wave, and
show how it yields an (; -approximation scheme for Union
Counting in any sliding window up to a prespecied maximum
window size N . We then sketch the proof of the approximation
guarantees, which uses the main error analysis
lemma from [13]. Finally, we show the time and space
bounds.
Let N 0 be the minimum power of 2 that is at least 2N ; let
be the desired error probability. Each
maintains a basic randomized wave for its stream,
consisting of d one for each
level
We use a pseudo-random hash function h to map positions
to levels, according to an exponential distribution. For
1=2 d . h() is computed as follows: we consider the numbers
as members of the eld
In a preprocessing step, we choose q and r uniformly and
independently at random from G and store them with each
party. In order to compute h(p), a party computes
Party receiving a stream bit b:
1. Increment pos. (Note: All additions and comparisons
are done modulo N 0 .)
2. Discard any position p in the tail of a queue that has
expired (i.e., p  pos N ).
3. If
parties use the same function h.)
(a) If the level l queue Q j (l) is full, then discard the
tail of Q j (l).
(b) Add pos to the head of Q j (l).
Answering a query for a sliding window of size n
N , after each party has observed pos bits:
1. Each party j sends its wave, fQ
to the Referee. Let s := max(0; pos
pos] is the desired window.
2. For j := be the minimum level such that
the tail of Q j (l j ) is a position p  s.
3. Let l  := max j=1;::: ;t l j . Let U be the union of all
positions in Q1 (l
4. Return ^
jU \ W j.

Figure

randomized wave algorithm for Union
Counting in a sliding window (t streams).
operations being performed in G). We represent
x as a d-bit vector and then h(p) is the largest y
such that the y most signicant bits of x are zero (i.e.,
[0::d]. The two properties
of h that we use are: (1) x is distributed uniformly over
G. Hence the probability that h(i) equals l (where l < d) is
exactly 1=2 l+1 . (2) The mapping is pairwise independent,
i.e., for distinct p1 and p2 , Pr
k2g. This is the same hash
function we used in [13], except that the domain and range
sizes now depend only on the maximum window size N and
not the entire stream length.
The steps for maintaining the randomized wave are summarized
in the top half of Figure 6. A 1-bit arriving in
position p is selected into levels h(p). The sample
for each level, stored in a queue, contains the c= 2 most
recent positions selected into that level. 36 is a constant
determined by the analysis; we have not attempted to
minimize c.) Consider a queue Q j (l), whose tail (earliest
element) is at position i. Then Q contains all the 1-bits
in the interval [i; pos] whose positions hash to a value greater
than or equal to l. We call this the range of Q j (l). As we
move from level l to l + 1, the range may increase, but it
will never decrease. For any window of size at most N , the
queues at lower numbered levels may have ranges that fail
to contain the window, but as we move to higher levels, we
will (with high probability) nd a level whose range contains
the window.
The bottom half of Figure 6 summarizes the steps for
answering a query. We receive a query for the number of
1's in the interval Each
initially selects the lowest numbered level l j such
that the range of Q contains W (step 2). Let l  be the
maximum of these levels over all the parties. Thus at each
the range of Q j (l  ) contains W . This implies that
each queue contains the positions of all the 1-bits in W in
its stream that hash to a value at least l  . We take the
union of the positions in the t queues, to form the queue
for level l  of the position-wise OR of the streams (step 3).
The algorithm returns the number of positions in this queue
that fall within the window W , scaled up by a factor of 2 l
(step 4).
Lemma 2. The algorithm in Figure 6 returns an estimate
for the Union Counting problem for any sliding window of
size n  N that is within a relative error of  with probability
greater than 2=3.
Proof. For each level l, dene S
(b maintains the positions of the
most recent 1's in S j (l). Consider the size of the overlap
of S j (l) and W . This is large for small l (because the
probability of selecting a 1-bit in W for S j (l) is 1=2 l ), and
decreases as l increases. If the overlap at level l is greater
than c= 2 , then W contains a position not among the c= 2
most recent positions of S j (l). On the other hand, if the
overlap is less than or equal to c= 2 , then the range of Q
contains W . Thus, l j (the level selected by P j ) is the minimum
level such that jS j (l) \ W j  c= 2 .
In other words, we are progressively halving the sampling
probability until we are at a level where the number of points
in the overlap is less than or equal to c= 2 . This very random
process has been analyzed in our previous paper [13]
(though in a dierent scenario). Thus, the lemma follows
from Lemma 1 in [13].
By taking the median of O(log(1=-)) independent instances
of the algorithm, we get our desired (; -approximation
scheme:
Theorem 4. The above estimation procedure is an (; -
approximation scheme for the Union Counting problem for
any sliding window of size at most N , using O( log(1=-) log 2 N
bits per party. The time to process an item is dominated by
the time for an expected O(log(1=-)) nite eld operations.
Proof. For each of the O(log(1=-)) instances, we have
O(log N) queues of O(1= 2 ) positions, and each position is
O(log N) bits. Also, for each instance, we have the hash
function parameters, q and r, which are O(log N) bits each.
Note that the approximation guarantees hold regardless of
the number of parties.
The per-item processing is O(1) expected time per instance
because the expected number of levels to which each
new position is added (step 3) is bounded by 2, and likewise
the expected number of levels that position
was ever in is bounded by 2. Thus scanning the tails of
the queues at levels looking for p (step 2) takes
constant expected time.
4.2 Improvements in Query Time
The query time for the above estimation procedure is the
time for the Referee to receive and process O(t log(1=-) log N
memory words. If all queries were for window size N , each
could easily keep track of the minimum level l j at
which the range of Q contains the window, with constant
processing time overhead. When a query is requested,
determining l  , the Referee
retains only those positions p in the queues that both
fall within the window and have h(p)  l  . (To avoid recomputing
h(p), h(p) could be stored in all queues containing
p.) In this way, the Referee computes Q j (l  ) \ W for each
explicitly receiving Q j (l  ) from party P j . It
takes the union of these retained positions and returns the
estimate ^ x as before. This reduces the query time to O(t= 2 )
time per instance, while preserving the other bounds.
5. EXTENSIONS
Number of Distinct Values. With minor modica-
tions, the randomized wave algorithm can be used to estimate
the number of distinct values in a sliding window over
distributed streams. An item selected for a level's sample
is now stored as an ordered pair (p; v), where v is a value
that was seen in the stream and p is the position of the most
recent occurrence of the value. This is updated every time
the value appears again in the stream. A sample at level l
stores the c
pairs with the most recent positions that were
sampled into that level. Note that, in contrast to the Union
Counting scheme, the hash function now hashes the value
of the item, rather than its position.
Each party maintains pos, the length of its observed stream.
It also maintains a (doubly linked) list of all the pairs in its
wave, ordered by position. This list lets the party discard
expired pairs.
When an item v arrives, we insert (pos; v) into levels
h(v). If v is already present in the wave, we update its
position. To determine the presence of a value in the wave,
we use an additional hash table (hashed by an item's value)
that contains a pointer to the occurrence of the value in
the doubly linked list. Updating a value's position requires
moving its corresponding pair from its current position to
the tail of the list, and this can be done in constant time.
The value's position has to be updated in each of the levels to
which it belongs. A straightforward argument shows that all
this per-item processing can be done in constant expected
time, because each value belongs to an expected constant
number of levels.
To produce an estimate, each party passes its wave to
the Referee. The Referee constructs a wave of the union
by computing a level-wise union of all the waves that it re-
ceives. This resulting wave is used for the estimation. As
before, we perform O(log(1=-)) independent instances of the
algorithm, and take the median. The space bound and approximation
guarantees follow directly from the arguments
in the previous section. Putting it altogether, we have:
Theorem 5. The above estimation procedure is an (; -
approximation scheme for the number of distinct values in
a sliding window of size N over distributed streams. It uses
O( log(1=-) log N log R
bits per party, where values are in [0::R],
and the per-item processing time is dominated by the time
for an expected O(log(1=-)) nite eld operations.
Handling Predicates. Note that our algorithm for distinct
values counting stores a random sample of the distinct
values. This sample can be used to answer more complex
queries on the set of distinct values (e.g., how many even distinct
values are there?), where the predicate (\evenness") is
not known until query time. In order to provide an (; -
approximation scheme for any such ad hoc predicate that
has selectivity at least  (i.e., at least an  fraction of the
distinct values satisfy the predicate), we store a sample of
size O( 1
) at each level, increasing our space bound by a
factor of 1
. Such problems without sliding windows were
studied in [10].
Nth Most Recent 1. We can use the wave synopsis
to obtain an (; -approximation scheme for the position of
the Nth most recent 1 in the stream, as follows. Instead
of storing only the 1-bits in the wave, we store both 0's
and 1's. Thus, items in level l are 2 l positions apart, not
l 1's apart. In addition, we keep track of the 1-rank of
the 1-bit closest to each item in the wave. The rest of the
algorithm is similar to our Basic Counting scheme. Note
that we need O(
log 2 (m)) bits, where m is an upper bound
on the window size needed in order to contain the N most
recent 1's.
Other Problems. Our improved time bounds for Basic
Counting and for Sum over a single stream lead to improved
time bounds for all problems which reduce to these
problems, as described in [4]. For example, an -approx-
imation scheme for the sliding average is readily obtained
by running our sum and count algorithms (each targeting a
relative error of
6.



--R

The space complexity of approximating the frequency moments.
Sampling from a moving window over streaming data.
Reductions in streaming algorithms
Maintaining stream statistics over sliding windows.
An approximate L 1
Testing and spot-checking of data streams
Probabilistic counting algorithms for data base applications.
An approximate L p
On computing correlated aggregates over continual data streams.
Distinct sampling for highly-accurate answers to distinct values queries and event reports
New sampling-based summary statistics for improving approximate query answers
Synopsis data structures for massive data sets.
Estimating simple functions on the union of data streams.



Clustering data streams.
Computing on data streams.
Stable distributions
Personal communication
On randomized one-round communication complexity
Communication Complexity.
Private vs. common random bits in communication complexity.
Public vs. private coin ips in one round communication games.
A note on counting distinct elements in the streaming model.
--TR
Probabilistic counting algorithms for data base applications
Private vs. common random bits in communication complexity
Public vs. private coin flips in one round communication games (extended abstract)
Communication complexity
New sampling-based summary statistics for improving approximate query answers
The space complexity of approximating the frequency moments
On randomized one-round communication complexity
Synopsis data structures for massive data sets
Testing and spot-checking of data streams (extended abstract)
On computing correlated aggregates over continual data streams
Space-efficient online computation of quantile summaries
Estimating simple functions on the union of data streams
Data-streams and histograms
Reductions in streaming algorithms, with an application to counting triangles in graphs
Sampling from a moving window over streaming data
Maintaining stream statistics over sliding windows
Surfing Wavelets on Streams
Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports
An Approximate Lp-Difference Algorithm for Massive Data Streams
An Approximate L1-Difference Algorithm for Massive Data Streams
Clustering data streams
Stable distributions, pseudorandom generators, embeddings and data stream computation

--CTR
Linfeng Zhang , Yong Guan, Variance estimation over sliding windows, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
Edith Cohen , Martin Strauss, Maintaining time-decaying stream aggregates, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.223-233, June 09-11, 2003, San Diego, California
Michael H. Albert , Alexander Golynski , Angle M. Hamel , Alejandro Lpez-Ortiz , S. Srinivasa Rao , Mohammad Ali Safari, Longest increasing subsequences in sliding windows, Theoretical Computer Science, v.321 n.2-3, p.405-414, August 2004
Abhinandan Das , Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Distributed set-expression cardinality estimation, Proceedings of the Thirtieth international conference on Very large data bases, p.312-323, August 31-September 03, 2004, Toronto, Canada
Edith Cohen , Haim Kaplan, Efficient estimation algorithms for neighborhood variance and other moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Brain Babcock , Mayur Datar , Rajeev Motwani , Liadan O'Callaghan, Maintaining variance and k-medians over data stream windows, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.234-243, June 09-11, 2003, San Diego, California
Edith Cohen , Martin J. Strauss, Maintaining time-decaying stream aggregates, Journal of Algorithms, v.59 n.1, p.19-36, April 2006
Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA
Sumit Ganguly, Counting distinct items over update streams, Theoretical Computer Science, v.378 n.3, p.211-222, June, 2007
L. K. Lee , H. F. Ting, Maintaining significant stream statistics over sliding windows, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.724-732, January 22-26, 2006, Miami, Florida
Arvind Arasu , Gurmeet Singh Manku, Approximate counts and quantiles over sliding windows, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Izchak Sharfman , Assaf Schuster , Daniel Keren, A geometric approach to monitoring threshold functions over distributed data streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
Edith Cohen , Haim Kaplan, Spatially-decaying aggregation over a network: model and algorithms, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Arvind Arasu , Jennifer Widom, Resource sharing in continuous sliding-window aggregates, Proceedings of the Thirtieth international conference on Very large data bases, p.336-347, August 31-September 03, 2004, Toronto, Canada
Brian Babcock , Chris Olston, Distributed top-k monitoring, Proceedings of the ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Edith Cohen , Haim Kaplan, Spatially-decaying aggregation over a network, Journal of Computer and System Sciences, v.73 n.3, p.265-288, May, 2007
Yishan Jiao, Maintaining stream statistics over multiscale sliding windows, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1305-1334, December 2006
Lukasz Golab , M. Tamer zsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June
waves;sliding windows;distributed;data streams