Sensing the Pulse of a Data Stream in Real Time – Transcript

00:00Welcome everyone. In this talk uh we will sense the pulse of a data stream like uh Twitter posts, credit card transactions or internet of things sensor readings in three ways.

00:16First we will cover the DGIM algorithm which is a clever bitbased strategy for approximating the count of ones in a sliding window.

00:29Second, we will see how to compute moments from data streams. We will learn how to estimate statistical moments like mean, variance and skewess using compact sketches.

00:46So we do all these without storing the entire data set in one pass and with limited memory. And last but not the least, we will discuss how to identify trending items with exponential decay. We'll discover how exponential decaying windows help surface emerging trends by giving more

01:09weight to recent data. So this is a crucial method for dynamic environments like social media or sensor networks. So this is very unlike the traditional uh uh data landscape. Uh traditional databases expect finite data.

01:31Uh so you can pause and analyze but streams never pause. Streams are continuously coming in. So we need smart lightweight methods that estimate things on the fly without storing everything.

01:50So sensing the pulse is a beautiful metaphor. We want to monitor a living beating data stream in real time while detecting trends and abnormalities as they happen.

02:08So the rest of the talk will show clever algorithms that trade a little accuracy for enormous gains in speed and memory.

02:20So let us dive in. So a good introduction to the concepts of data streams, sketches and counting is provided in this talk that I gave a couple of months ago. Uh you can check if you are interested. But you should be able to fairly follow through today's talk even if you did not watch it.

02:46I'll uh cover some basics. Uh so this is the video. Uh anyway, I'll not play it. You can watch it. You can search uh I have a YouTube channel and you can search there.

03:01Okay. So the first algorithm is about counting from strings. Suppose data comes u continuously and we want to know how many distinct things have we seen for instance uh unique you users visiting a site so this is a stream so we can't store

03:28all users it's too expensive so there is an algorithm called flag Martin algorithm which I talked uh which I discussed in the video that I showed previously It proposes a probabilistic trick.

03:43So flag Martin provides a quick guess for cardinality of a stream using clever tricks. But uh it is not a precise count. Uh big data is all about approximations.

03:58Approximate it's big data is essentially an approximate science. What we do is probabilistic counting of distinct elements. So the idea is we hash each element.

04:13Each element is like each event. It when we say stream, it's a stream of events. Typically the event could be a credit card transaction or it could be a user visiting a site. All those are events and those streams of events are continuously flowing in. So what we do is we hash each of these events. uh a an

04:36event is represented by a tpple, right? You know what a tpple is, right? Um so it's represented by a tpple and uh it's also called element. So we hash each of these tpples and look at the position of the least significant one bit in the binary hash.

04:59So we convert uh first we hash the event to a table uh and then uh we look at the least significant bit which is set.

05:15That is because the probability of getting that bit pattern gives us statistical information about how many unique items we have seen. So that's really ingenious. I mean no nobody would it's it's not very apparent um but somebody could see that uh um the least significant bit that is set when a number is converted into its

05:42binary equivalent tells you some statistical information. So that is the crux of this algorithm. uh and uh of course we need to average over multiple hash functions because uh we cannot trust any hash function. So we use multiple hash functions and we average it out and we surprisingly get

06:06accurate estimate of the cardality using just a few uh bytes. So this is one of the important milestones in streaming algorithms. It showed that approximation can beat exactness when resources are tight.

06:24So I'll I'll I'll spend a few minutes uh detailing it. So um so uh let me first explain the intuition right. So suppose uh we are uh for every element that is coming in the stream we are tossing a set of coins

06:47right. So if the coin is turns heads the bit is set and if that coin turns tails it is set to zero. Right? So there are a set of coins. So what this algorithm assumes and it was proven also is that the position of the first heads corresponds to how rare that hash outcome is.

07:16So the more unique items you see the higher the chance that one of them will have a long run of trailing zeros. So the largest such run tells you roughly how big your set is.

07:33So the algorithm elegantly turns randomness into an estimator of distinct count. So the real magic is that we only need to store the maximum observed zero run length.

07:50Right? the number of zeros is what we are going to store not the whole data set. So that's what makes it scale. So so that is the intuition but the algorithm itself is very simple even much simpler than the intuition. So first is we hash every element in the stream uh to a number and we convert that

08:14number into a bit string. So this bit string is typically constant like 128 bits, 256 bits and so on. So this is straightforward right? We use a hash function. We convert the tpple into a number right. Uh so some more details I explained in the previous video in case you are not familiar about hashing.

08:39And uh so once we convert uh convert the event into a bit string we count the trailing zeros from the start from the ending. So for each hashed element the number of trailing zeros in the bit string is recorded and then uh we have uh a number of events have come through and we have hashed them. We need to keep track of

09:06the maximum number of trailing zeros across all elements R. That's it. That is the algorithm. Suppose the maximum number of um um uh trailing uh suppose the hash current the current hash number is uh 16 right 16 is one followed by three zeros.

09:33Uh so what is the maximum number of trailing zeros we have seen so far? It is three right? Uh one followed by three zeros. So we just keep track of that number and next time when suppose 33 comes the number of zeros the trailing zeros will increase to four I believe right?

09:58Yeah four. um because 33 has uh uh I believe four zeros right um so that is the idea we keep track of we just keep track of the maximum number of trailing zeros across all all all elements and then the number of distinct elements n is estimated by the formula 2 power r that's it so if