本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。
基数计数(cardinality counting)通常用来统计一个集合中不重复的元素个数，例如统计某个网站的UV，或者用户搜索网站的关键词数量。数据分析、网络监控及数据库优化等领域都会涉及到基数计数的需求。 要实现基数计数，最简单的做法是记录集合中所有不重复的元素集合S_uSu，当新来一个元素x_ixi，若S_uSu中不包含元素x_ixi，则将x_ixi加入S_uSu，否则不加入，计数值就是S_uSu的元素数量。这种做法存在两个问题：
当统计的数据量变大时，相应的存储内存也会线性增长
当集合S_uSu变大，判断其是否包含新加入元素x_ixi的成本变大
大数据量背景下，要实现基数计数，首先需要确定存储统计数据的方案，以及如何根据存储的数据计算基数值；另外还有一些场景下需要融合多个独立统计的基数值，例如对一个网站分别统计了三天的UV，现在需要知道这三天的UV总量是多少，怎么融合多个统计值。
基数计数(cardinality counting)通常用来统计一个集合中不重复的元素个数，例如统计某个网站的UV，或者用户搜索网站的关键词数量。数据分析、网络监控及数据库优化等领域都会涉及到基数计数的需求。 要实现基数计数，最简单的做法是记录集合中所有不重复的元素集合S_uSu，当新来一个元素x_ixi，若S_uSu中不包含元素x_ixi，则将x_ixi加入S_uSu，否则不加入，计数值就是S_uSu的元素数量。这种做法存在两个问题：
当统计的数据量变大时，相应的存储内存也会线性增长
当集合S_uSu变大，判断其是否包含新加入元素x_ixi的成本变大
大数据量背景下，要实现基数计数，首先需要确定存储统计数据的方案，以及如何根据存储的数据计算基数值；另外还有一些场景下需要融合多个独立统计的基数值，例如对一个网站分别统计了三天的UV，现在需要知道这三天的UV总量是多少，怎么融合多个统计值。