有效地计算大型数据集中的共现

Question

最近遇到了这个面试编程测试:

• 您将获得1000位用户最喜爱的50位艺术家名单(来自last.fm)
• 生成一起出现至少50次的所有艺术家对的列表.
• 解决方案无法存储在内存中,也无法评估所有可能的对.
• 解决方案应该可以扩展到更大的数据集.
• 解决方案不一定非精确,即您可以报告很有可能满足截止值的对.

我觉得我有一个非常可行的解决方案,但我想知道他们是否在寻找我错过的特定内容.

(如果它有所作为 - 这不是我自己的面试,所以我不是想欺骗任何未来的雇主)

以下是我的假设:

• 有最大数量的艺术家(根据MusicBrainz为622K),而用户数量没有限制(嗯,不超过70亿,我猜).
• 艺术家遵循"长尾"分布:一些是受欢迎的,但大多数受到极少数用户的青睐.
• 选择截止值来选择一定比例的艺术家(大约1%,50和给定数据),因此随着用户数量的增加它将增加.

第三个要求有点模糊 - 从技术上讲,如果你有任何确切的解决方案,你"评估了所有可能的对".

实用解决方案

1. 第一遍:将艺术家姓名转换为数字ID; 将最喜欢的数据存储在临时文件中; 记录每位艺术家的用户收藏.

   需要string-> int map来跟踪指定的id; 如果空间比速度更重要,则可以使用Patricia树(需要1/5空间和两倍于我的时间,不可否认,测试不是很严格).

2. 第二遍:迭代临时文件; 抛弃那些没有单独地满足截止值的艺术家; 保持2d矩阵中的对数.

   将需要n(n-1)/2字节(或短路,或整数,取决于数据大小)加上数组参考开销.应该不是问题,因为n最多是622K的0.01-0.05.

这似乎可以使用少于100MB的内存处理任何大小的真实数据集.

替代解决方案

如果您不能进行多次传递(出于任何人为的原因),请使用Bloom过滤器数组来保持对数:对于您遇到的每对,找到它(可能)的最高过滤器,并添加到下一个最高过滤器.所以,第一次将它加到bf [0],第二次加到bf [1],依此类推,直到bf [49].或者可以恢复在某一点之后保持实际计数.

我没有运行数字,但最低的几个过滤器将相当大 - 这不是我最喜欢的解决方案,但它可以工作.

还有其他想法吗？

Answer 1

您应该考虑挖掘关联规则的现有方法之一。这是一个经过充分研究的问题，本土解决方案不太可能更快。一些参考：

1. 维基百科有一个不错的实现列表http://en.wikipedia.org/wiki/Association_rule_learning。

2. 引用我之前的回答：What is the most effective way to access certain elements in a SortedSet? 。

这里有一个现有实现的存储库： http: //fimi.ua.ac.be/src/。这些是几年前参加性能比赛的工具；其中许多都附有指示性论文来解释它们如何/何时/为何比其他算法更快。