有序组合算法

Question

我有以下任务:

• 有10M个文档
• 有 10 万个唯一标签
• 每个文档有 100 个标签

对于每个标签 X，我需要找到前 10 个 Y 标签，其中 X 和 Y 都出现在文档中，按 X 和 Y 同时出现的文档数量排序。

这个任务似乎很难解决:

• 虽然结果集对于 100K 个标签每个只有 10 条记录
• 保持所有组合的简单算法对内存使用非常敏感:(X,Y) 的总组合有 0.5*10^12 种，它增长为 n^2，其中 n 是标签的数量

有没有什么方法可以解决这个问题，而不用将所有组合都保存在内存中，或者使用并行算法(类似于 map reduce)来解决？如果我不需要它 100% 准确怎么办？

Answer 1

我认为在一般情况下，您将无法避免非常糟糕的运行时间 - 每个文档中有 5050 对，10M 文档，所有组合似乎都是可能的。

但是，在典型的现实世界数据中，您很少需要处理“对抗性”输入。一种可能的解决方案是首先计算所有 100K 项的出现次数，对它们进行排序，然后针对每个项 X，执行以下操作:

• 如果有很多带有 X 的文档(即，不少于文档计数的 1%，或其他一些可调整的部分)，以 X 和 Y 的形式对您的索引运行查询，从最流行的术语开始，然后继续向下，保持大小为 10 的堆来跟踪最受欢迎的对。您知道 max(docs with X & Y) = max(docs with X, docs with Y)，因此您很可能能够尽早缩短此过程
• 如果带有 X 的文档很少，则更谨慎的做法是简单地浏览带有该术语的所有文档并自行汇总总数。

对于一个行为良好的文档集，其中 100K 项遵循关于文档计数的对数曲线，您将做的工作远远少于 (100)^2 * 10M 的工作，而天真的解决方案在所有情况下都需要这样做。诚然，对于性能不佳的文档集，您最终会做更多的工作，但这在现实世界中不应该发生。

至于“不是 100% 准确”，这个规范太模糊了，无法使用。什么样的错误是允许的？有多少？

---评论响应(评论太大)---

a) 考虑确定 1 亿个元素的最大值。您只需要保存扫描时最好的 1 个 - 同样的原则适用于确定 N 个项目中的前 X 个。将传入的元素添加到一个二叉堆中，当堆的大小超过X时，移除最弱的元素。添加结束，你将拥有顶部的X

b) 假设您正在确定前 10 个 X&Y 对，其中 X="Elephant"。假设在扫描 1000 个 Y 术语后，你有一个大小为 10 的堆，其中最小得分对的计数为 300。现在假设你检查的第 1001 个术语的文档计数为 299 - 因为只有 299 个文档有 Y 术语，最多299 个文档也有 X&Y，因此它不可能比你目前拥有的前 10 对中的任何一个更好，并且由于所有 Y 术语都按文档频率排序，事实上你现在知道你没有检查更多对!这就是 max 语句向您保证的。

c) 您为每个 X 做出的选择纯粹是一个优化决策。如果您有许多只存在于少量文档中的 X，那么这是一个很好的问题 - 这意味着每学期的工作量更少。

d) 如果您可以接受前 10 名错误的非零概率(对于每个术语)，您可以通过使用抽样方法而不是完整、严格的扫描来减少运行时间索引。术语 X 在文档索引中越普遍，在根据您收集的信息可能拥有正确的前 10 个 X&Y 对之前，您必须(按比例)扫描的文档越少。得出这方面的确切数字需要了解相关索引中术语的预期分布。特别是:术语有多少相关性？数字 N(X)/MAXY(X) 通常是什么样子的，其中 N(X) 是包含术语 X 的文档数，MAXY(X) 是包含 X&Y 对的文档数，最大化所有项 Y != X