Scribd
Upload
510 views16 pages

Sliding and Decaying Window Algorithms

Uploaded by

kharshitha93
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
510 views16 pages

Sliding and Decaying Window Algorithms

Uploaded by

kharshitha93
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Sliding Windows

Sliding window is a useful model of stream processing in which the


queries are about a window of length N – the N most recent
elements received.
In certain cases N is so large that the data cannot be stored in
memory, or even on disk. Sliding window is also known as

Consider a sliding window of length N=6 on a single


stream as shown in figure 1. As the stream content
varies over time the sliding window highlights new
stream elements.

Figure 1. Sliding window on stream


Example1: Consider Amazon online transactions. For
every product X we keep 0/1 stream of whether that
product was sold in the n-th transaction. A query like,
“how many times have we sold X in the last k sales?”
and an answer for it can be derived using sliding
window concept.

Now let us suppose we have a window of


length N (say N=24) on a binary system, We
want at all times to be able to answer a query
of the form “ How many 1’s are there in the
last K bits?” for K<=N.

Here comes the DGIM Algorithm into


picture:

COUNTING THE NUMBER OF 1’s IN THE


DATA STREAM

DGIM algorithm (Datar-Gionis-Indyk-


Motwani Algorithm)

Designed to find the number 1’s in a data


set. This algorithm uses O(log²N) bits to
represent a window of N bit, allows to
estimate the number of 1’s in the window
with an error of no more than 50%.

So this algorithm gives a 50% precise answer.

In DGIM algorithm, each bit that arrives has a


timestamp, for the position at which it arrives.

if the first bit has a timestamp 1, the second bit


has a timestamp 2 and so on.. the positions are
recognized with the window size N (the window
sizes are usually taken as a multiple of
2).The windows are divided into buckets
consisting of 1’s and 0's.

RULES FOR FORMING THE


BUCKETS:

1. The right side of the bucket should


always start with 1. (if it starts with
a 0,it is to be neglected) E.g. ·
1001011 → a bucket of size
4 ,having four 1’s and starting with
1 on it’s right end.
2. Every bucket should have at least
one 1, else no bucket can be
formed.
3. All buckets should be in powers of
2.
4. The buckets cannot decrease in
size as we move to the left. (move in
increasing order towards left)

Let us take an example to understand the


algorithm.

Estimating the number of 1’s and


counting the buckets in the given data
stream.
This picture shows how we can form the
buckets based on the number of ones by
following the rules.

In the given data stream let us assume


the new bit arrives from the right. When
the new bit = 0
After the new bit ( 0 ) arrives with a time
stamp 101, there is no change in the
buckets.

But what if the new bit that arrives is 1,


then we need to make changes..
· Create a new bucket with the current
timestamp and size 1.

· If there was only one bucket of size 1,


then nothing more needs to be done.
However, if there are now three buckets
of size 1( buckets with timestamp
100,102, 103 in the second step in the
picture) We fix the problem by combining
the leftmost(earliest) two buckets of size
1.

To combine any two adjacent buckets of


the same size, replace them by one
bucket of twice the size. The timestamp
of the new bucket is the timestamp of the
rightmost of the two buckets.

Now, sometimes combining two buckets


of size 1 may create a third bucket of size
2. If so, we combine the leftmost two
buckets of size 2 into a bucket of size 4.
This process may ripple through the
bucket sizes.

How long can you continue doing this…

You can continue if current timestamp-


leftmost bucket timestamp of window <
N (=24 here) E.g. 103–87=16 < 24 so I
continue, if it greater or equal to then I
stop.

Finally the answer to the query.

How many 1’s are there in the last 20


bits?

Counting the sizes of the buckets in the


last 20 bits, we say, there are 11 ones.

In a decaying window, you assign a score or


weight to every element of the incoming data
stream.
Decaying Window Algorithm
This algorithm allows you to identify the most
popular/trending elements in an incoming data
stream.

The decaying window algorithm not only tracks


the most recurring elements in an incoming data
stream, but also discounts any random spikes or
spam requests that might have boosted an
element’s frequency.
In a decaying window, you assign a score or
weight to every element of the incoming data
stream.
Further, you need to calculate the aggregate sum
for each distinct element by adding all the
weights assigned to that element. The element
with the highest total score is listed as trending
or the most popular.

weights

timet
1. Assign each element with a weight/score.
2. Calculate aggregate sum for each distinct
element by adding all the weights assigned to
that element.

In a decaying window algorithm, we assign


more weight to newer elements. For a new
element, you first reduce the weight of all the
existing elements by a constant factor k and then
assign the new element with a specific weight.
The aggregate sum of the decaying exponential
weights can be calculated using the following
formula:

∑t-1 at−i(1−c)i
i=0
Here, c is usually a small constant. Whenever a
new element, say at+1, arrives in the data stream
you perform the following steps to achieve an
updated sum:
1. Multiply the current sum/score by the
value (1−c).
2. Add the weight corresponding to the new
element.

Weight decays exponentially over time

In a data stream consisting of various elements,


you maintain a separate sum for each distinct
element. For every incoming element, you
multiply the sum of all the existing elements by
a value of (1−c). Further, you add the weight of
the incoming element to its corresponding
aggregate sum.

A threshold can be kept to, ignore elements of


weight lesser than that.
Finally, the element with the highest aggregate
score is listed as the most popular element.
Example
For example, consider a sequence of twitter tags
below:
data stream [fifa, ipl, fifa, ipl, ipl, ipl, fifa]

Also, let's say each element in sequence has


weight of 1.
Let's c be 0.1
The aggregate sum of each tag in the end of
above stream will be calculated as below:
Fifa SCORE
fifa - 1 * (1-0.1) = 0.9
ipl - 0.9 * (1-0.1) + 0 = 0.81 (adding 0 because
current tag is different than fifa)
fifa - 0.81 * (1-0.1) + 1 = 1.729 (adding 1
because current tag is fifa only)
ipl - 1.729 * (1-0.1) + 0 = 1.5561
ipl - 1.5561 * (1-0.1) + 0 = 1.4005
ipl - 1.4005 * (1-0.1) + 0 = 1.2605
fifa - 1.2605 * (1-0.1) + 1 = 2.135
ipl SCORE
fifa - 0 * (1-0.1) = 0
ipl - 0 * (1-0.1) + 1 = 1
fifa - 1 * (1-0.1) + 0 = 0.9 (adding 0 because
current tag is different than ipl)
ipl - 0.9 * (1-0.01) + 1 = 1.81
ipl - 1.81 * (1-0.01) + 1 = 2.7919
ipl - 2.7919 * (1-0.01) + 1 = 3.764
fifa - 3.764 * (1-0.01) + 0 = 3.7264

In the end of the sequence, we can see the score


of fifa is 2.135 but ipl is 3.7264
So, ipl is more trending than fifa
Even though both of them occurred same
number of times in input there score is still
different.
Advantages of Decaying Window
Algorithm:
1. Sudden spikes or spam data is taken care.
2. New element is given more weight by this
mechanism, to achieve right trending output.

Reference:
[Link]
2018/12/[Link]

Common questions

Powered by AI

The decaying window algorithm differentiates itself in handling spikes or spam by decreasing the weight of existing elements over time exponentially, thus making the score of older data less impactful compared to newer data. This mechanism effectively dampens the influence of sudden spikes or spam, thereby maintaining a more consistent representation of truly trending elements within a stream .

The DGIM algorithm uses a bucket-based buffering strategy for buffering continuous data streams, where buckets denote sections of the stream starting with '1' and following strict size rules to maintain buffer efficiency on streams of binary data . In contrast, the decaying window algorithm applies a score or weight to each element that decays exponentially over time, focusing on more recent elements to identify trending items. This approach effectively filters noise and adjusts scores dynamically as new elements arrive .

The decaying window algorithm uses exponential decay for updating the scores of elements. The aggregate sum of the decaying weights is calculated by multiplying the current scores by (1−c), with 'c' being a small constant. The updated score for a new element is obtained by adding its weight to the score after decay has been applied to all existing scores .

The core rules for bucket formation in the DGIM algorithm include starting each bucket with a '1', ensuring each bucket contains at least one '1', having bucket sizes as powers of 2, and ensuring bucket sizes do not decrease towards the left. These rules are significant because they help minimize storage usage by creating a compact representation of the data stream, ensuring that the system can handle large window sizes efficiently by allowing easy combination and summation of bucket contents to approximate the count of '1's in the stream .

Consider a sequence with elements having an initial weight of 1. When a new element arrives, each existing element’s score is multiplied by (1-c), where c=0.1, before adding the weight of the new element. For instance, if 'fifa' had a previous score of 0.9 and is incoming again, its score becomes 0.9*(1-0.1) + 1 = 1.729, effectively increasing its score more than other elements in this context .

Weight assignment in the decaying window algorithm promotes identification of trending topics by assigning more weight to newer data, and reducing the weight of older data exponentially as new entries arrive. This dynamic adjustment ensures that recent data has more influence on the total score, allowing the system to more accurately reflect current trends and discount outdated spikes .

When a new '1' arrives and the window already contains multiple buckets of the same size, the DGIM algorithm requires merging the leftmost (earliest) two buckets of the same size into one larger bucket. This process can ripple through, potentially combining larger buckets if the condition propagates, maintaining the efficient storage and accurate count of 1’s in the data stream .

The DGIM algorithm controls memory usage by representing a stream of N bits using only O(log²N) bits. It forms buckets that contain bits, ensuring each bucket begins with a '1' and follows specific rules such as maintaining bucket sizes as powers of 2 and not decreasing in size to the left. This method of bucketing reduces the storage requirement to approximate the count of 1’s in the window with a bounded error of no more than 50% .

Systems might implement the DGIM algorithm over maintaining a full data history due to its efficient use of memory and ability to maintain data summaries with reduced storage demand. This is especially advantageous in real-time processing of large streams where storing full data is impractical due to size constraints while still allowing for approximate queries with acceptable error margins .

The sliding window model allows for real-time processing by focusing the computation on the most recent data elements, thus making the system efficient and responsive to recent changes. When the size of the window exceeds available memory, the model introduces algorithms like DGIM, which use compact data structures to maintain a summary of the data using fewer resources than storing the entire window .

You might also like