Streaming model

Definition

• Input: stream of n elements
• Goal: do one pass through the stream (or only a few passes), use a small memory (e.g. O(1) or O(log n)) and answer a specific query about the stream
  • Good for processing very fast streams, such as IP packets passing a router or measurements of a very low-powered device
  • Not enough memory to store the whole stream, each item should be processed fast
• Strict turnstile model:
  • underlying set {0,...,n-1}
  • virtual vector F of length n initialized to zeroes
  • stream consists of operations (j,x) meaning F[j]+=x
  • At every point we have F[j]>=0 for each j
• Cash register model: all values x are positive
• Example: if all values x are +1, we are simply counting frequencies of elements from {0,...,n-1} on input

Count-Min sketch

• Strict turnstile model
• CM sketch with parameters epsilon and delta
• Array of counters A of depth $d=\lceil \ln(1/\delta )\rceil$ and width $w=\lceil e/\epsilon \rceil$
• Each row i of A has a hash function h_i from {0,...,n-1} to {0,...,w-1} (assume totally random, but a weaker assumption of pairwise independence sufficient for analysis)
• Update (j,x) does A[i,h_i(j)]+=x for all hash function i=0,...,n-1
• Query F[j]=? returns min_i A[i,h_i(j)]
• Let F be the correct answer, F' the answer returned
• Clearly F'>=F, because each A[i,k] may have contributions from other elements as well
• With probability at least 1-delta we have $F'[j]\leq F[j]+\epsilon \sum _{i}F[i]$
• Proof:
  • Let $M=\sum _{k}F[k]$
  • for a fixed row i: $E[A[i,h_{i}(j)]=F[j]+\sum _{{k\neq j}}F[k]/w$, because every other element k has probability 1/w to hash to column h_i(j) and thus it cntributes F[k]/w to
  • $E[A[i,h_{i}(j)]\leq F[j]+M\epsilon /e$
  • By Markov inequality $\Pr(A[i,h_{i}(j)]-F[j]\geq M\epsilon )\leq 1/e$
  • Probability that this happens in every row i is at most $e^{{-d}}\leq \delta$
• Memory does not depend on n
• Note: if we insert million elements and then delete all but 4 of them, in the final structure we are very likely to be able to identify the 4 remaining ones as M is only 4