我们目前正面临一个有趣的问题 . 我们想要一个集合的基数而不需要存储每一个项目（通常位图/位集是一个很好的方法） . 一个非常好的算法是所谓的HyperLogLog随机算法（更多信息请参见http://antirez.com/news/75） .
这里的问题是，你只能将集合合并为 UNIONs ，所以基本上它是 OR 组合 .
我们实际上不仅要将集合与OR组合，还要与AND组合 . 我们甚至想要结合这些操作 .
Example: set1 AND（set2 OR set3）OR（set4 AND set5）
每组可以具有数百万的基数 . 每个值的大小为128位 .
每组可以以任何方式表示，例如“HLL，布隆过滤器，简单列表或这些组合” . 算法必须使用可行的空间量在尽可能短的时间内执行 .
有任何想法吗？
1 回答
这个确切的问题是https://pdfs.semanticscholar.org/5da8/bf81712187712aed159aed62e38fb012872e.pdf的主题 . 他们建议使用bloom过滤器 .
union的bloom过滤器是bloom过滤器的按位OR . 用于交叉的布隆过滤器是布隆过滤器的按位AND . 因此，您可以轻松生成所需操作的布隆过滤器 .
他们的定理1允许您根据布隆过滤器中设置的位数来估计集合的大小 .