https://micvog.com/2015/07/18/frequency-counting-algorithms-over-data-streams/
https://blog.csdn.net/dm_ustc/article/details/46051091
https://www.afenxi.com/20042.html
http://dmac.rutgers.edu/Workshops/WGUnifyingTheory/Slides/cormode.pdf
Simplified version: – Track items and counts – For each block of 1/ε items, merge with stored items and counts – Decrement all counts by one, delete items with zero count ♦ Easy to see that counts are accurate to εN ♦ Analysis shows O(1/ε log εN) items are stored ♦ Full version keeps extra information to reduce error
SpaceSaving Algorithm
“SpaceSaving” algorithm [Metwally, Agrawal, El Abaddi 05] merges Lossy Counting and FREQUENT algorithms ♦ Keep k = 1/ε item names and counts, initially zero Count first k distinct items exactly ♦ On seeing new item: – If it has a counter, increment counter – If not, replace item with least count, increment count
https://blog.csdn.net/dm_ustc/article/details/46051091
https://www.afenxi.com/20042.html
比如，一个社交网站上有上亿的用户主页，而且每天有上十亿的访问量，想实时知道最常被访问的主页有哪些，然后给出一个排名。常用的做法是给每个主页一个计数器，这样需要很大的内存(往往装不下)来保存这些计数器，但极大多数的计数器其实只有一次两次，这是一个非常大的浪费，而且现实资源不允许这么做。
再比如，一个网站有海量的IP访问。为了检测爬虫或是DOS，需要计算一个IP在一个时间单位(比如一分钟，一小时，一天，等)中访问的次数，然后屏蔽或是captcha单位时间内访问次数过多的IPs。由于web server中能用来统计IP访问次数的内存资源有限，不可能存储所有的访问IPs。
还有很多类似的例子，比如，一段时间内的流行商品，一段时间内的人气王，经常被拨打的电话，作弊的账号，等等。
对于这些实时数据流的频率统计问题，有在数学上可能保证错误小于某个要求值的近似算法，Lossy Counting Algorithm 就是 Gurmeet Singh Manku 提出和证明的一个算法。
这些问题都可以统一为以下的问题描述，对于一个数据流，找出所有的频率大于某个值(通常表示为总数的百分比，这里用s表示)的所有元素，进而可以找出top n。
Lossy Couting 算法的第一步是将数据流分成一样大小的很多个窗口(或是片)。窗口的大小和期望的错误率息息相关。之后具体讨论。
从第一个窗口开始，计算每个元素的频率。注意了，高明之处来了，在窗口结束时，将每个元素的计数减一，然后将哪些计数值为零的元素从内存中删除。这样在保证近似性的同时也限制了内存资源的占用。妙吧!
然后，处理下一个窗口中的元素，同样，在窗口的结束时，将每个元素的计数减一，同时清除那些计数为零的元素。直到所有数据处理完毕，或是实时流数据的检查点到了。最后，将内存中的元素按频率排序，就能得当当前的top n。
很明显，Lossy Counting 算法是个近似算法，但它的错误是可以分析和数学上可以证明它的边界的。如果错误率是e，窗口大小为1/e(哈哈，这样才能保证错误率小)，对于长度为N的流，有N/(1/e)=eN 个窗口，由于每个窗口结束时减一了，那么频率最多被少计数了窗口个数eN。
最后留下的元素是频率超过 sN-eN的。近似算法能保证：
- 频率最多被少算eN;
- 没有错误的反例(不应该出来的元素出来了);
- 错误的正例有的真实频率至少是sN-eN。
最后，内存的使用的最坏情况是 1/e log (eN) 个计数器。参考阅读原文看证明。
http://dmac.rutgers.edu/Workshops/WGUnifyingTheory/Slides/cormode.pdf
Simplified version: – Track items and counts – For each block of 1/ε items, merge with stored items and counts – Decrement all counts by one, delete items with zero count ♦ Easy to see that counts are accurate to εN ♦ Analysis shows O(1/ε log εN) items are stored ♦ Full version keeps extra information to reduce error
SpaceSaving Algorithm
“SpaceSaving” algorithm [Metwally, Agrawal, El Abaddi 05] merges Lossy Counting and FREQUENT algorithms ♦ Keep k = 1/ε item names and counts, initially zero Count first k distinct items exactly ♦ On seeing new item: – If it has a counter, increment counter – If not, replace item with least count, increment count
