Cardinality Counting

Cardinality Counting，基数计数，可以理解为广义上的UV统计。当你需要计算某维度下的用户个数、商品个数等各种需要去重（unique）的统计量时，就需要用到基数计数技术。

考察一个基数计数方法的优劣，主要需要考虑插入速度、计数速度、合并速度以及空间消耗四个方面。

假设如下一个应用场景：我们希望获得年龄、性别、地域、种族等多个维度叉乘下的用户数量，并且能够自由选择维度进行聚合并得到相关的用户数量。

bitmap

bitmap是用一个长bit串来存储所有用户的出现情况。

插入时可以直接定位到对应的bit[O(1)]，计数只需统计1的个数[O(N)]，多维度聚合时也只需将多个bit串做或操作即可[O(N)]。所以，这里插入速度、计数速度、合并速度均可以接受。

但是，bitmap在空间消耗上是不紧凑的：假设我们有1000W用户，那么无论当前维度组合下的实际用户数量有多少（即使只有1个用户），我们都至少需要1000W个bit，即大约1.2MB的空间来存储。这显然是极大的浪费。考虑上面的维度组合，20(年龄区间数）x2（性别）x300（地级市级别）x56（民族）x1.2M=787.5GB，这还是只有四个维度，1000W用户的情况。

当然，我们也可以采用分维度单独存储bitmap的形式（维度组合时采用与而非或的操作），但是这也需要空间（20 + 2 + 300 + 56） * 1.2M = 453.6M。实际情况下，维度往往多很多，用户数量也可能更多，并且为了考虑未来用户数量的增长，往往需要更多的bit位数，所以bitmap在空间消耗这一点上是有问题的。

b-tree

我们也可以参考数据库索引的方式，使用b-tree来存储不同维度下的用户信息。

b-tree在查找和插入方面均是O(logM)的复杂度，计数为O(M)，空间消耗为O(logM)。注意，这里的M为当前维度组合下的用户数量M，而非上述bitmap中的用户总数量N，一般情况下M

但是，b-tree不能高效的进行合并操作：合并两个b-tree相当于重建一颗b-tree。所以使用b-tree时，我们无法高效的进行自由维度的聚合操作。

总结

那么，有没有一种方法可以在这四项中都取得优异的表现呢？

注意，这里bitmap和b-tree给出的统计值都是精确值。如果在数据量非常大的情况下，我们可以损失一些精度，来换取这四项的优秀表现。这类算法就是基数估计算法。其中最具有代表性的就是LogLog Counting和HyperLogLog Counting算法。后面我会找时间总结一下这类算法。