logo标签列表

快速近似算法用于集合交集的基数

algorithmindexingdata-structureshashlanguage-agnostic
8
我有一个包含n个元素的池集合，但所有集合都无法放入RAM。我只能将其中的一小部分（例如1-5%）放入RAM中。
问题是，给定查询集合Q，我需要返回与Q相交基数最大的前k个集合。
  1. 假设Q来自相同的池集合。
  2. 对于普通的Q。
k很小，只有几百个，而n则有数千万个。所有集合中不同元素的总数也有数千万个。
  • 有许多概率数据结构，如KMV、MinHash及其变种，我应该使用哪个？
  • 我能否修改HyperLogLog以适应我的任务？
  • 这些结构中哪些可以组装成某种索引？
我尝试将集合表示为布隆过滤器进行实验。由于集合大小差异很大，我必须使用非常大的布隆过滤器，这是低效的（布隆过滤器占用原始数据集的5倍空间）。来自https://github.com/jaybaird/python-bloomfilter的自适应布隆过滤器仅能压缩数据集3-5倍，因此这仍然几乎不可行。
1
“所有集合都不适合RAM”是指a）没有集合适合RAM，还是b）所有集合的组合都不适合RAM？ - Marcus Müller
这意味着 b)。我可以将约 1% 的所有数据集放入内存中。 - Moonwalker
4个回答
4

K-Minimum Values数据结构非常节省内存。与布隆过滤器不同，它不提供成员测试，只提供集合操作和基数估计。

根据您集合的基数和误差容忍度，可能适合您使用。

2
链接的文档中没有关于HyperLogLog的内容。您能解释一下将HLL与MinHash相乘的含义吗？您是指仅仅将两个集合的估计基数相乘吗？您能否提供一个链接，表明这样做可以达到您想要的效果？ - mac01021
2
将所有集合保存在一个布隆过滤器中，包含形式为(setId, value)的键。这个布隆过滤器必须能够处理所有集合的并集大小，这样可以避免将小集合存储在为非常大的集合大小而设计的布隆过滤器中。
其次，为了达到你的目的，你可能接受非常高的错误率，这也使得布隆过滤器缩小。一个1%错误率的布隆过滤器每个元素需要9.58505837736744...比特。一个10%错误率的布隆过滤器每个元素需要4.79252918868372比特。但是如果你有一个10%的错误率，在一个400个元素的集合上，经过纠正预期的假阳性后，你可以得到一个答案，95%的时间内与正确答案相差不超过3%。这可能是可以接受的，以获得过滤器大小减少一倍的效果。（Q越大，相对误差越小。）
如果以上两种技术仍然使布隆过滤器过大，那么也许你应该考虑将数据分布在多台机器上...
1
如果您将查询集Q保存在内存中作为哈希表，则无需同时将所有其他集保存在内存中。您可以依次计算每个集的交集基数。只需将一个集加载到内存中，计算其与Q的交集基数，最后再将其从内存中删除即可。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接