我有一个池集(池大小为 n)，所有集都不适合 RAM。我只能适应一小部分，比如所有集合的 1-5% 到 RAM 中。
问题是给定查询集 Q 我需要返回与 Q 相交的最大基数的前 k 个集。
- 假设 Q 来自同一个集合池。
- 对于一般问题。
k很小，以百为单位，而n以亿为单位。所有集合中的区域元素总数也以数亿计。
- 有很多概率数据结构，KMV，MinHash，它是 变体，我应该使用哪一个？
- 我可以修改 HyperLogLog 吗？ 任务？
- 哪些结构可以组装成某种索引？
我做了一些将集合表示为布隆过滤器的实验。因为集合大小变化很大，所以我必须使用非常大的 bloomfilters，这是低效的(bloomfiltes 占用原始数据集的 5 倍空间)。来自 https://github.com/jaybaird/python-bloomfilter 的自适应 bloomfiter仅对数据集产生 3-5 倍的压缩，因此这仍然非常不可行。
最佳答案
K-Minimum Values数据结构的内存效率极高。与布隆过滤器不同，它不提供成员资格测试，仅提供集合论运算和基数估计。
可能适合您，具体取决于您的集合的基数和您的容错能力。
关于algorithm - 集交集基数的快速近似算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37629899/