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算法。后面我会找时间总结一下这类算法。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180505G0JP4F00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

同媒体快讯

扫码关注腾讯云开发者

领取腾讯云代金券