我有一个池集(大小为池n)，所有集都不适合RAM。我只能将一小部分，比如说所有集合的1-5%放入RAM。
问题是给定查询集Q，我需要返回与Q相交基数最大的前k个集。
- 假设Q来自同一集合池
- 对于一般Q
k很小，以数百为单位，而n以数亿为单位。所有集合中的区域元素总数也以数亿计。
- 有许多概率数据结构，KMV、MinHash和变体，我应该使用哪一个
- 我可以修改我的HyperLogLog吗任务
- 哪些结构可以组合成某种索引
我做了一些实验，将集合表示为bloom过滤器。由于集合大小变化很大，我不得不使用非常大的布隆过滤器，这是低效的(布隆过滤器占用原始数据集的5倍空间)。来自https://github.com/jaybaird/python-bloomfilter只对数据集进行3-5倍的压缩，所以这仍然非常不可行。
K-Minimum Values数据结构非常节省内存。与Bloom过滤器不同，它不提供成员测试，只提供集合论运算和基数估计。
可能对您有用，这取决于集合的基数和您的容错能力。
将所有集合一起保存在一个包含形式为(setId, value)的键的布隆过滤器中。这必须能够处理所有集合的并集大小的集合，这使您无法将小集合存储在适合非常大集合的布隆过滤器中。
其次，出于你的目的，你可能会接受非常大的错误率，这再次让bloom过滤器缩小。错误率为1%的布隆滤波器每个元件需要9.58505837736744…位。具有10%错误率的布隆滤波器每个元件需要4.79252918868372比特。但是，如果你有10%的错误率，在一个400元素的集合中，在纠正了预期的假阳性后，你可以得到95%的时间在正确答案的3%以内的答案。这可能是可以接受的，以获得滤波器大小的因子2的减小。(Q越大，相对误差越小。)
如果在这两种技术之间，bloom过滤器仍然太大，那么也许你应该考虑在多台机器上分发数据。。。
实际上，我已经找到了解决方案。通过将hyperloglog和minhash相乘得到交集，minhashes可以有效地与LSH一起存储。更多详细信息请点击此处：http://infolab.stanford.edu/%7Eullman/mmds/ch3.pdf
如果将查询集Q作为哈希表保存在内存中，则无需同时将所有其他集保存在内存。您可以一个接一个地计算每个集合的交集基数。只需将一个集合加载到内存中，计算其与Q相交的基数，最后将其再次从内存中删除。