So we would like to solve the heavy hitters problem in a data stream. So once you design a small space data structure, you can scan a stream of data items, i1, i2 through iN. And at the end of the stream, output the k most frequent items that occurred. We also want this data structure to have a small space complexity. We want space requirements at most, order k log N. Well formally, we would like to design a small space data structure that solves the following problem. We call it FindTop. FindTop scans an input stream S of items, and has a parameter k in hand. At the end of the stream, it outputs the top k most frequent items that it saw in this tree. Well it turns out to be useful to first design a primitive for the following related problem. We call it PointQuery. PointQuery is a small space data structure hopefully, that scans the stream S. And at the end of the stream gets a query i. i is a data item. And in response, outputs the frequency fi. That is the number of terms that i occurred in the stream. Well for simplicity, we'll assume that the data items are ordered in descending order of their current frequency of occurrence in the stream. So, item one is the most frequent item. Item two is somewhat less frequent, etc., etc. What we want to design is a data structure that can solve PointQuery, scan the stream, and then answer queries at the end. And we want this data structure to use small space, space on the order of k log N. Where k is the number of items we will be ultimately looking for in the stream. Well unfortunately this turns out to be impossible in general. And this is because, as stated, we require this PointQuery and FindTop to output exact answers. Well, imagine a stream where every data item occurs with roughly the same probability, or rather roughly the same frequency. It seems very hard to design a small space data structure to figure out which items were exactly the top k. And this can be proved formally that one essentially needs to store the entire stream. So what we definitely need is a notion of approximation if we want to get sublinear space complexity. To that effect, we define the following approximate version of the problem. We call it find approximate top. So this has two parameters k, the number of items that we're looking for, and the precision parameter epsilon. At the end of the stream, this procedure needs to return a set of k elements, such that for every data item i that we report at the end of the stream, the frequency that i occurred within the stream is not much smaller than the frequency of the actual kth most frequent element. So fi should be at least (1- epsilon)fk, where fk is the number of times the kth most frequent element occurred. And now again it turns out to be very useful to design a procedure for the following approximate version of the PointQuery problem. So here we want to scan the stream. At the end of the stream, if given a query i, we want to report an approximation at hat i to the number of times item item i occurred in the stream. This approximation should be off by at most an additive epsilon fk term. Or again, if k is the number of times, the kth dominant element occurred. Okay, so this looks better. At least we have a notion for approximation. Now unfortunately, as stated, this is still a hard problem. And indeed, if we still imagine a stream where all the items occur roughly with the same frequency, maybe up to 1 plus minus epsilon, this is still a hard problem to solve. One essentially needs to store most of the stream. So in fact, in this lecture, we will design a small space primitive for both of these problems. That will allow us to find these top k elements, top k most frequent elements in the stream, assuming that they actually contribute a bulk of the stream in a certain sense. And we will see the formal formulation of what this means to contribute the bulk of the stream later in this lecture.
