Finding Frequent Items in Data Streams - School of 寻找数据流中的频繁项学院.pptVIP

Finding Frequent Items in Data Streams Moses Charikar Princeton Un., Google Inc. Kevin Chen UC Berkeley, Google Inc. Martin Franch-Colton Rutgers Un., Google Inc. Presented by Amir Rothschild Presenting: 1-pass algorithm for estimating the most frequent items in a data stream using very limited storage space. The algorithm achieves especially good space bounds for Zipfian distribution 2-pass algorithm for estimating the items with the largest change in frequency between two data streams. Definitions: Data stream: where Object oi appears ni times in S. Order oi so that fi = ni/n The first problem: FindApproxTop(S,k,ε) Input: stream S, int k, real ε. Output: k elements from S such that: for every element Oi in the output: Clarifications: This is not the problem discussed last week! Sampling algorithm does not give any bounds for this version of the problem. Hash functions We say that h is a pair wise independent hash function, if h is chosen randomly from a group H, so that: Let’s start with some intuition… Idea: Let s be a hash function from objects to {+1,-1}, and let c be a counter. For each qi in the stream, update c += s(qi) Realization Claim: For each element Oj other then Oi, s(Oj)*s(Oi)=-1 w.p.1/2 s(Oj)*s(Oi)=+1 w.p. 1/2. So Oj adds the counter +nj w.p. 1/2 and -nj w.p. 1/2, and so has no influence on the expectation. Oi on the other hand, adds +ni to the counter w.p. 1 (since s(Oi)*s(Oi)=+1) So the expectation (average) is +ni. That’s not enough: The variance is very high. O(m) objects have estimates that are wrong by more then the variance. First attempt to fix the algorithm… t independent hash functions Sj t different counters Cj For each element qi in the stream: For each j in {1,2,…,t} do Cj += Sj(qi) Take the mean or the median of the estimates Cj*Sj(oi) to estimate ni. Still not enough Collisions with high frequency elements like O1 can spoil most estimates of lower frequency elements, as Ok. The solution !!! Divide Conquer: Don’