西方最快的集合运营

Question

我无法在一个地方找到任何令人满意的关于这个主题的报道,所以我想知道:什么是最快的交集,联合和分离算法？
有限域名是否有任何有趣的？
任何人都可以击败O(Z),其中Z是交叉点的实际大小？

如果您的方法依赖于排序集,请注意,但不要将其视为不合格因素.在我看来,必须有一个真正的微妙优化仓库来分享,我不想错过任何一个.

我知道的一些算法依赖于vanilla之外的按位运算,因此您可以假设存在SSE4并访问popcount等内在函数.请注意这个假设.

有趣的是: BY Intersect的实现

更新
我们有一些非常好的部分答案,但我仍然希望对这个问题有更完整的攻击.我特别感兴趣的是看到更明确地使用布隆过滤器来解决这个问题.

更新
我已经完成了一些关于将bloom过滤器与cuckoo哈希表相结合的初步工作.它看起来几乎令人讨厌,因为它们有非常相似的需求.我已经接受并接受了答案,但此刻我并不满意.

Answer 1

如果您愿意考虑类似集合的结构，那么布隆过滤器具有简单的并集和相交操作。