基数估计算法

Linear Counting

该算法用于估测数据基数，也就是说有多少不同元素，采用方法非常简单，将数据哈希到长度为m的数组，访问到的位置就置为1

我们可以近似认为哈希的结果服从均匀分布，那么最后设集合基数为n的最大似然估计为\(−m\cdot ln(\frac{u}{m}) \)，其中u为哈希表中0的个数

论文：- Whang, Kyu-Young, Brad T. Vander-Zanden, and Howard M. Taylor. “A linear-time probabilistic counting algorithm for database applications.” ACM Transactions on Database Systems (TODS) 15.2 (1990): 208-229.

FM Sketch（PCSA）

该算法是基于概率来估计基数，首先我们根据数据随机情况观察二进制的性质，可以发现末尾有\(k\)个连续0的情况出现次数是按比例缩小的，因此我们基于这个观察得出估计方法

首先我们随机一个哈希函数将数据映射到一个二进制长度为\(L\)的空间内（即\([0,2^L-1]\) ），我们记录BITMAP来标记是否出现一个数后尾恰好有连续\(i\)个0，这样显然根据访问的概率就可以估计数据基数，我们取在bitmap中第一个为0的位置，即我们没有映射后末尾恰好有\(k\)个0的key，因此我们用\(k\)来近似\(\log n \)，显然这样数据是偏小的，论文根据计算添加了偏差参数\(E(k)=\log\phi n,\phi=0.77351\cdots\)

显然这样还是不太准确，于是就采用了多次哈希的方式，我们利用得到的\(k\)的均值来进行估计

论文：Flajolet, Philippe, and G. Nigel Martin. “Probabilistic counting algorithms for data base applications.” Journal of computer and system sciences 31.2 (1985): 182-209.

LogLog

顾名思义，就是利用loglogn的空间来实现估测基数的算法。可以说基本就是FM的优化，我们记录\(p(x)\)表示对于想哈希之后末尾有\(p(x)\)个0，那么其实我们只需要记录\(max(p(x))\)即可，因此该空间为loglogn的

那么同样，我们可以采用将数据随机分桶统计，通过求max的平均值来估测

HyperLogLog算法使用调和平均值将它们组合成原始基数的估计值

参考：https://zhuanlan.zhihu.com/p/271186546

基数估计算法（包括HLL、AC）

Kmin

KMV Sketch是用于统计数据流中不同元素个数，显然直接统计空间开销是O(n)的，该算法利用了随机哈希的性质来近似的估计

首先，我们假设存在一个非常优美的哈希，他将数据均匀的分布在了[0,1]的区间内，这样我们发现我们只需要考虑离0最近的点的距离，就可以估测具体有多少个值被哈希进来，即（1/最近距离）

但是这样显然会有较大的误差，因此我们采用前k小的点来估测，那么最后我们取(k-1)/max(KMV)为答案

这里的“-1”修正的具体推导可以参见论文

参考：https://agkn.wordpress.com/2012/07/09/sketch-of-the-day-k-minimum-values/

Misra-Gries

该算法用于查找频繁项，我们基于给定频率，以一定误差为代价来节约空间，近似找到所有出现次数大于该频率的项

考虑和找概率超过一半元素的思想类似，我们维护k个桶，先填满之后末尾淘汰，新来的项如果不在里面我们即可能应该舍弃，这时我们即实际上少记录了一次，那么我们将桶内的所有count-1，来保证相对稳定

这样在桶内的大概率为频繁项，但是频繁项一定在桶中

参考：https://en.wikipedia.org/wiki/Misra%E2%80%93Gries_summary

Bloom Filter

布隆过滤器用于近似找到一个元素是否在给定集合内出现，即实现粗“过滤”操作。

同样采取哈希的方式，我们为了减小哈希冲突，将一个元素哈希到不同位置，那么我们认为这些位置全部被置1才为集合内元素

论文：Bloom, Burton H. “Space/time trade-offs in hash coding with allowable errors.” Communications of the ACM 13.7 (1970): 422-426.

Counting Bloom Filter

我们发现bloomfilter对于静态集合有较优的性能，但是我们无法在集合中进行删除元素，因为我们并不知道删除之后是否将对应位置0

因此我们引入了计数器，将之前的赋值变成了+1，这样我们删除的时候在对应位置-1即可

CM Sketch

count min sketch利用多个哈希函数，将数据流进行哈希，也就是说内部结构为一个h*w的数组表示h个位置，用w个哈希函数

我们每次更新即在每个哈希对应位置加上当前的size
此时我们发现由于存在哈希冲突每个位置对应值必然会受到其他的影响而变大
因此我们取这w个的最小值作为我们的预估值

论文：Cormode, Graham, and Shan Muthukrishnan. “An improved data stream summary: the count-min sketch and its applications.” Journal of Algorithms 55.1 (2005): 58-75.

Count Sketch

考虑对于每个桶会有其他元素的哈希冲突导致计数偏大，我们想尽可能减少其影响
这里我们同样采用一个哈希函数h映射到w个桶中，之后我们新随机一个哈希函数g将n个值随机映射为{-1,1}
这样我们将加法计数操作变为\( C[h(i)]+=c\cdot g(i) \)，这样我们基于随机的方式，考虑其他对该位置影响的元素是随机进行加减记录的，因此减小了其影响
这样我们查询操作就变成了返回\(g(i)\cdot C[h(i)] \)

当然这样的操作仍存在很大的随机偏差，因此我们采用多个哈希函数，即记录与计算多次，对于查询操作取对于每组哈希的对应查询的均值

论文：M. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data streams. Automata, languages and programming, pages 784–784, 2002.

CU Sketch

CU Sketch 只是对于CM 进行了微小的改动，即变成了“保守更新”。在更新的时候，把之前对于每个counter进行加法的操作变成了只对于最小的counter做+1，这样显然正确性还可以保证，并且大幅提升了准确度，但显然就失去了对于删除操作的支持。

论文：- C. Estan and G. Varghese. New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice. ACM Transactions on Computer Systems (TOCS), 21(3):270–313, 2003.

LD Sketch

算法用于检测heavy hitter和heavy changer，基于了分布式系统设计了算法，并且利用弹性数组来节约内存使用。

同样采用了多个哈希函数的方式，和朴素的相比，对于每个位置多维护了弹性数组A记录具体信息以及其大小l（指储存的不同键值个数）和桶内键值的最大估计误差e

这里l的大小我们桶的总val和设定阀值比值而弹性变换（具体可参考论文），那么数组A中信息更新参照上面Misra-Gries算法而进行末尾淘汰，从而维护频繁项的较具体信息，并且我们维护e的信息即累计在Misra-Gries算法实现中数组整体减小的总值

那对应heavy hitter检测就变成对于每个哈希函数查询对应估值的上界，如果都大于设定阀值则判断为正

分布式检测：首先将数据通过哈希随机到一个大小为\(d\)的worker集合中，显然对于同一键值必然始终在一个集合，然后让远程站点选择一个worker进行发送数据，这样每个站点平均收到了\(1/d\)，我们修改一下阀值（并添加了一个修正参数？），那么我们对于hh的检测就变成了让每个站点全部都为正反馈才为真

论文：- Huang, Qun, and Patrick PC Lee. “Ld-sketch: A distributed sketching design for accurate and scalable anomaly detection in network data streams.” IEEE INFOCOM 2014-IEEE Conference on Computer Communications. IEEE, 2014.

MV Sketch

我们发现ldsketch的动态内存难以实现，改算法采用了较小的静态内存构建

我们发现对于一个桶首先当桶数够多时基本最多只存在一个大流，并且这个大流必然占据大部分比例

因此与LDsketch类似，我们对于每个桶只新增维护heavy flow的键值和对应Misra-Gries算法的估值计数器，不过我们仅存最大值且把加减1变成了对应val

对于查询操作我们即返回相应估值

论文：- Tang, Lu, Qun Huang, and Patrick PC Lee. “Mv-sketch: A fast and compact invertible sketch for heavy flow detection in network data streams.” IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019.

FlowRadar

该算法主要为小内存来存储数据流计数器并通过解码来分析数据流。这样显然我们就需要记录对应的key。那么为了可以解码，我们需要使用可逆的压缩方式，就是加法和的组合异或。

对于更新操作，我们首先利用bloom filter来记录存在多少个不同的流，即是否为新的key，之后利用CM计数，同时我们维护对于key的信息，（因为CM进行多次哈希存在）我们对于每个counter都存一个对应key的安位异或值，也就是说每进入的一个新的key都与之前的信息进行异或，同时我们也存储有几个不同的key

那么这样我们如果存在一些桶只有一个key，那么他存的对应值必为其的精确信息，我们就可以利用这个信息继续恢复其他数据。即我们可以将其对应的所有桶都删去该值的信息，这样也就有可能会再有一些桶只剩一个key，如此往复一直到恢复不了或者结束。

那么这样也显然对于分布式机器也很方便，我们将本地的可解数据发给其他人来利用这个信息继续解码，这样不断循环直到没有新的可解码数据

论文：- Li, Yuliang, et al. “Flowradar: A better netflow for data centers.” 13th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 16). 2016.

UnivMon

主要思想就是分层降采样，按照数据流大小来分成log层，每次二分之一的概率随机选取进行采样，这样我们得到了log个子流，

ElasticSketch