User:Normalrobot33/sandbox

In the field of streaming algorithms, Misra–Gries summaries are used to solve the frequent elements problem in the data stream model. That is, given a long stream of input that can only be examined once (and in some arbitrary order), the Misra-Gries algorithm can be used to compute which (if any) value makes up a majority of the stream, or more generally, the set of items that constitute some fixed fraction of the stream.

The term "summary" is due to Graham Cormode. The algorithm was presented by Misra and Gries alongside a different algorithm for finding frequent elements, the Misra–Gries heavy hitters algorithm.

The Misra–Gries summary

As for all algorithms in the data stream model, the input is a finite sequence of integers from a finite domain. The algorithm outputs an associative array which has values from the stream as keys, and estimates of their frequency as the corresponding values. It takes a parameter k which determines the size of the array, which impacts both the quality of the estimates and the amount of memory used.

algorithm misra-gries:
    input: 
        A positive integer k
        A finite sequence s taking values in the range 1,2,...,m
    output: An associative array A with frequency estimates for each item in s
    
    A := new (empty) associative array
    while s is not empty:
        take a value i from s
        if i is in keys(A):
            A[i] := A[i] + 1
        else if |keys(A)| < k - 1:
            A[i] := 1
        else:
            for each K in keys(A):
                A[K] := A[K] - 1
                if A[K] = 0:
                    remove K from keys(A)
    return A

Error analysis

Due to the required space constraints, when the algorithm reaches the limit of the size of the associated data structure $A$, some frequencies may be reduced, resulting in the output frequency ${\hat {f}}_{i}$ not matching the actual frequency $f_{i}$. The specific range of the error is:

$f_{i}-{\frac {m}{k}}\leq {\hat {f}}_{i}\leq f_{i}$

Upper bound

Since each time an element $i$ appears in stream, the value of the key corresponding to this element $A[i]$ will increase by at most one, we have:

${\hat {f}}_{i}\leq f_{i}$

Lower bound

An intuitive explanation: Each time we perform the "minus one" operation, we will reduce the counters of the $k$ elements currently tracked in $A$ by $1$, reducing a total of $k$ units. These units are gradually accumulated by our previous "increment one" operations. Therefore, each "minus one" can be regarded as undoing $k$ "increment one".

The stream has a total of $m$ elements, and at most $m$ "increment one" operations can occur. Therefore, at most ${\frac {m}{k}}$ "minus one" can occur. Hence we have the lower bound:

$f_{i}-{\frac {m}{k}}\leq {\hat {f}}_{i}$

Properties

The Misra–Gries algorithm uses O(k(log(m)+log(n))) space, where m is the number of distinct values in the stream and n is the length of the stream. The factor k accounts for the number of entries that are kept in the associative array A. Each entry consists of a value i and an associated counter c. The counter c can, in principle, take any value in {0,...,n}, which requires ⌈log(n+1)⌉ bits to store. Assuming that the values i are integers in {0,...,m-1}, storing them requires ⌈log(m)⌉ bits.

Every item which occurs more than n/k times is guaranteed to appear in the output array. Therefore, in a second pass over the data, the exact frequencies for the k−1 items can be computed to solve the frequent items problem, or the majority problem. With the same arguments as above, this second pass also takes O(k(log(m)+log(n))) space.

The summaries (arrays) output by the algorithm are mergeable, in the sense that combining summaries of two streams s and r by adding their arrays keywise and then decrementing each counter in the resulting array until only k keys remain results in a summary of the same (or better) quality as compared to running the Misra-Gries algorithm over the concatenation of s with r.

Solve majority problem

In practice, the majority problem can be solved by setting $k\geq 2$ and running Misra-Gries Algorithm in two passes.(Strictly speaking, the second pass is not the Misra–Gries algorithm, but a normal counting pass. Beacuse the second pass accurately counts the elements from output of the first pass)

First, according to the lower bound of the error, ${\hat {f}}_{j}\geq f_{j}-{\frac {m}{k}}$, where $j$ is the majority and $f_{j}>{\frac {m}{2}}$. Hence ${\hat {f}}_{j}\geq f_{j}-{\frac {m}{k}}>{\frac {m}{2}}-{\frac {m}{k}}\geq 0$, if and only if $k\geq 2$.

Since it has been proved that ${\hat {f}}_{j}>0$, the majority $j$ must be in the result of the first pass output. However, we can not know which element is the majority in one pass because of the error.

In the second pass, counters are maintained only for $k-1$ elements in the output of the first pass, and count exactly the number of times when each element appears. If the frequency of an element is greater than ${\frac {m}{2}}$, this element must be the majority.

Example

Let k=2 and the data stream be 1,4,5,4,4,5,4,4 (n=8,m=5). Note that 4 is appearing 5 times in the data stream which is more than n/k=4 times and thus should appear as the output of the algorithm.

Since k=2 and |keys(A)|=k−1=1 the algorithm can only have one key with its corresponding value. The algorithm will then execute as follows(- signifies that no key is present):

Example Execution of Misra–Gries

Stream Value	Key	Value
1	1	1
4	—	0 (full, the value of key 1 is reduced by 1, key 1 is removed)
5	5	1
4	—	0 (full, the value of key 5 is reduced by 1, key 5 is removed)
4	4	1
5	—	0 (full, the value of key 4 is reduced by 1, key 4 is removed)
4	4	1
4	4	2

First pass output (Misra-Gries output): (key=4, estimated frequency=2)

In second pass, only one counter is maintained for key $4$, which has a value of $5>{\frac {8}{2}}=4$. Hence key $4$ is the majority.

Second pass output: 4