| 词条 | Misra–Gries summary | |||||||||||||||||||||||||||
| 释义 |
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 twice (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 Misra–Gries summaryAs 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 {{var|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:{{sfn|Cormode|2014}} '''input:''' A positive integer {{var|k}} A finite sequence {{var|s}} taking values in the range 1,2,...,{{var|m}} '''output:''' An associative array {{var|A}} with frequency estimates for each item in {{var|s}} {{var|A}} := new (empty) associative array '''while''' {{var|s}} is not empty: '''take''' a value {{var|i}} from {{var|s}} '''if''' {{var|i}} is in keys({{var|A}}): {{var|A}}[{{var|i}}] := {{var|A}}[i] + 1 '''else if''' |keys({{var|A}})| < {{var|k}} - 1: {{var|A}}[{{var|i}}] := 1 '''else''': '''for each''' {{var|K}} in keys({{var|A}}): {{var|A}}[{{var|K}}] := {{var|A}}[{{var|K}}] - 1 '''if''' {{var|A}}[{{var|K}}] = 0: remove {{var|K}} from keys({{var|A}}) '''return''' {{var|A}}PropertiesThe Misra–Gries algorithm uses O({{var|k}}(log({{var|m}})+log({{var|n}}))) space, where {{var|m}} is the maximum value in the stream and {{var|n}} is the length of the stream. Every item which occurs at least {{var|n}}/{{var|k}} times is guaranteed to appear in the output array.{{sfn|Cormode|2014}} Therefore, in a second pass over the data, the exact frequencies for the {{var|k}}−1 items can be computed to solve the frequent items problem, or in the case of {{var|k}}=2, the majority problem. This second pass takes O({{var|k}}log({{var|m}})) space.{{Citation needed|date=November 2017}} The summaries (arrays) output by the algorithm are mergeable, in the sense that combining summaries of two streams {{var|s}} and {{var|r}} by adding their arrays keywise and then decrementing each counter in the resulting array until only {{var|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 {{var|s}} with {{var|r}}. Example{{Expand section|date=November 2017}}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{{Refbegin}}
External links
1 : Streaming algorithms |
|||||||||||||||||||||||||||
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。