Streaming model: Rozdiel medzi revíziami

Verzia zo dňa a času 17:27, 17. apríl 2017

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

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]\leq M\epsilon )\leq 1/e$
- Probability that this happens in every row i is at most $exp(-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

@@ Riadok 13: / Riadok 13: @@
 * Example: if all values x are +1, we are simply counting frequencies of elements from {0,...,n-1} on input
-===Count-Min sketch===
+==Count-Min sketch==
 * Strict turnstile model