computer science

Misra–Gries summary

Misra–Gries summary is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Misra–Gries summary rather than just read about it. In short: 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 s…

Key takeaways

Misra–Gries summary belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Misra–Gries summary to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Misra–Gries summary from memory before moving on to harder problems.

Reference excerpt

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

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 in the case of k=2, 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.

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):

Output: 4

References

Worked examples

Example 1 — a first encounter with Misra–Gries summary

Start with the simplest possible case. Write down what Misra–Gries summary claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Misra–Gries summary before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Misra–Gries summary ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Misra–Gries summary

In research: Misra–Gries summary appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Misra–Gries summary in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Misra–Gries summary is common in secondary-school and first-year university syllabi. It links to neighbouring topics Streaming algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Misra–Gries summary outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Misra–Gries summary” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Misra–Gries summary in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Misra–Gries summary means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Misra–Gries summary out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Misra–Gries summary in simple terms?

Why does Misra–Gries summary matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Misra–Gries summary?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Misra–Gries summary.