前言
基数计数（cardinality counting）是实际应用中的常见计算场景。基数是指一个集合中不同元素的个数，比如集合{1，2，3，4，7，8，1，2，4}有9个元素，其中1，2出现两次，因此此集合的基数为7.
实例
- 统计某个网站的独立访客
基于B树 确定算法
最为直观的方法就是将用某个存储结构将每个不同的元素都存储下来, 每个新的处理单元都与已有的元素做对比, 如果不存在则插入到存储结构中,最后统计存储结构的单元数量.
B树是其中一种存储结构, 查找和插入较为高效,
缺点
- B树不能高效的合并
BitMap 确定算法
算法步骤：
-
生成长度为N的BitMap：L
- 元素a处理，hash(a)到L中某一位，并置为1
- 重复步骤2，知道所有元素都处理
- 基数估计值为L中1的个数。
缺点
- bitmap的长度与集合中元素无关, 而与基数的上限有关. 这意味着对于每个集合都要分配上限的内存. 内存开销太大. 以淘宝为例, 记录上限为1亿的某个链接的基数,需要12.5M字节的bitmap, 对于淘宝,每个商家都有数十到上百的商品链接, 整个淘宝又有成千上万的商家,内存开销太大.
LinearCounting 概率算法
linearcounting在1990年的一篇论文“A linear-time probabilistic counting algorithm for database applications”中被提出. 算法步骤接近bitmap, 核心是理解其概率推导的过程。
实际上是对bitmap的一种改进，传统的bitmap要求L的长度N大于或等于集合所有元素的个数，以srcIP为例，地址空间为$2^{32}$, 那么需要的bit数量为$2^{32}$,这个数字太大了。LC就是一种概率型数据结构，允许不同元素的冲突，以近似的结果来实现内存的压缩。
算法步骤:
- 生成长度为m的bitmap，$N«{setNum}$
- 将集合中的元素映射到bitmap中的某一位，并设为1
- 重复步骤2，知道所有元素都处理完毕
- 统计bitmap中0的个数u，
- 基数估计值为：$n=-m\log{\frac{u}{m}}$
具体推理过程可见：http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-ii.html
Flajolet-Martin算法及变种PCSA
花了不少时间来区分FM和LL算法，实际上这两个算法都是由同一个作者提出，并且处理过程也非常相似。FM算法在1984年的论文《Probabilistic Counting Algorithms for Data Base Applications》提出.
前提：均匀随机化
对于哈希函数H具有以下的要求：
- hash结果具有很好的均匀性，即原始集合元素的分布不影响hash后结果的分布
- H’的碰撞几乎可以忽略不计
- H的hash结果是固定长度的
思想来源
假设a为集合中的一个元素hash后的结果。a可以看做一个固定长度的字符串，也就是a的二进制表示。将这L个bit位从左往右标记为1,2…,L
定义$p(a)$为a的二进制表示中，从末尾出现的第一个1的位置。
算法步骤：
- 生成长度为m的bitmap
- 集合中的元素a，hash之后{字符串长度为m}，取$p(a)$. 将bitmap中的$p(a)$ 位置设为1.
- 重复步骤2，直到集合中所有元素都被处理
- 将bitmap中0出现的最小下标即为R，则基数估计为$n=\frac{2^R}{\varphi}$, $\varphi \approx 0.77353$ {这是作者给的一个修正值}
PCSA
PCSA 全写为Probabilistic counting with stochastic averaging，基于离散平均值的概率性计数。
主要思路是FM中的bitmap拓展为m个组，每次hash时，以$h(a)\%m$确定组，$floor[h(a)/m]$确定下标。取m个组的平均值作为R，$R=(R_1+R_2+…+R_m)/m$, 基数估计值为$n=\frac{2^R}{\varphi}$.
LogLog
LogLog算法是在2003年的论文《Loglog Counting of Large Cardinalities》 首次提出。和FM非常相似，又有显著的不同。
$p(a)$ 在这里指的是二进制串，从左往右遇到的第一个1的位置下标。
算法步骤：
- 生成数量为m的，长度为的bitmap。
- 对于元素a，计算hash值$H(a)$, 将hash结果的前k个bit作为分桶，$k=\log{m}$ .
- 将$H(a)$的后L-k个作为参与基数估计的串，将$p(a)$位置设为1
- 重复2,3,；直到所有元素都被处理
- 对第s个桶，取bit为1的最大位置的下标$R_s$。取m个桶的平均值$R=(R_1+R_2+…+R_m)/m$.
- 最后的基数估计值为$n = \alpham2^R$
内存分析
假设基数上限为一亿，约$2^{27}$, 当分桶数m为1024时，每个桶的基数上限约为$2^{27}/2^{10} = 2^{17}$，因此每个桶需要基数的最大值为17，每个桶所需的bit最多为5bit，即$\log_{2}{(\log_2{(2^{17})})}$ . 所需要的总字节数为5*1024/8=640字节。这也是被称为loglog的原因。
Adaptive Counting
AC在论文《Fast and accurate traffic matrix measurement using adaptive cardinality counting》中被提出，核心思想很简单，就是LC和LLC的组合使用，因为LC在基数数量较小时效果较好，而LLC在基数数量较大时，内存一定下效果较好，因此AC根据基数的数量级决定使用LC和LLC。
阈值采用空桶率估计，设置空桶率为0.051.当空桶率大于0.051 采用LC；否则采用LLC。
HyperLogLog
HLL在论文《HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm》中提出，也是在LLC的基础上改进。
demo可见：http://content.research.neustar.biz/blog/hll.html
改进点1
使用调和平均数代替几何平均数。前面的分析可以看到LLC的R值是各个桶取算术平均
调和平均定义如下：
$H = \frac{n}{\frac{1}{x_1}+\frac{1}{x_2}+…+\frac{1}{x_n}}$
改进点2 分段偏差修正
n相对于m较小和较大时采用不同的修正方案。n为基数真实值，m为估计器的最大值。
内存分析
假设基数的范围为N，
- bitmap： bitmap需要bit数量与N相同，因此为O(N)
- LC: LC最重要的参数时bit数组的长度，一般而言为N的十分之一即可。
- 更具体地分析可以参考论文
- LL：计数器的范围为$log(N)$, 计数器的大小为$log(log(N))$, 假设分桶数为1024， N为1000000，则内存为$1024*log(log(N))\approx 5000bit \approx 0.5Kb$
- HLL: 内存效率和LL是类似的。
其他
误差修正的方法？还是无偏估计量的获得方法
研究这种问题的常用方法是使用生成函数（generating function）。通过运用指数生成函数和poissonization得到上述估计量的Poisson期望和方差
参考
- http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-iv.html
