集合相交基数的快速近似算法
我有一个池集(大小为n)，所有的集合都不适合RAM。我只能容纳一小部分，比方说，1-5%的所有设备进入RAM.
该问题是给定的查询集Q，需要返回与Q相交最大基数最大的上k集。
- 假设q来自相同的集合池。
- 对Q.
K是小的，有几百，而n在数亿。地区元素在所有集合中的总数也是数亿。
- 有很多概率数据结构，KMV，MinHash及其变体，我应该使用哪一个？
- 我可以为我的任务修改HyperLogLog吗？
- 哪一种结构可以组合成某种指标？
我做了一些实验，用布卢姆滤镜来表示布卢姆。由于集合大小变化很大，我不得不使用非常大的bloomfiltes，这是低效的(bloomfiltes占用原始数据集的5倍空间)。来自https://github.com/jaybaird/python-bloomfilter的自适应bloomfiters只对数据集进行3-5倍的压缩，因此这仍然是不可行的。
回答 4
Stack Overflow用户
发布于 2016-07-17 11:57:38
事实上，我已经找到解决办法了。在给定的交集中，加法和最小哈希相乘，最小哈希可以有效地用LSH存储。这里有更多详细信息：http://infolab.stanford.edu/%7Eullman/mmds/ch3.pdf
Stack Overflow用户
发布于 2016-06-08 00:58:42
K-最小值数据结构具有极大的内存效率。与Bloom过滤器不同，它不提供隶属度测试，只提供集合论运算和基数估计.
可能适用于您，这取决于集合的基数和错误容忍。
Stack Overflow用户
发布于 2016-07-14 20:22:20
将所有集合保存在一个包含表单(setId, value)键的花期过滤器中。这将必须能够处理所有集合的联合大小的集合，这将使您无法将小集存储在为非常大的集设置大小的花期过滤器中。
第二，出于您的目的，您可能会接受非常大的错误率，这再次让布卢姆过滤器收缩。一个错误率为1%的布卢姆滤波器需要9.58505837736744.每个元素的位。一个10%错误率的布卢姆滤波器每个单元需要4.79252918868372位。但是，如果你有一个10%的错误率，在一个400元素集上，你可以在纠正了预期的错误后，得到一个95%的答案，在正确答案的3%范围内。这可能是可以接受的，以获得2倍的缩小过滤器大小。(Q越大，相对误差就越小。)
如果在这两种技术之间，布卢姆过滤器仍然太大，那么也许您应该考虑将数据分布在多台计算机上。
https://stackoverflow.com/questions/37629899
复制相似问题
腾讯云开发者
