1

我有以下任务：

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

对于每个标签 XI 需要找到 10 个前 Y 标签，其中 X 和 Y 都存在于文档中，按 X 和 Y 都存在的文档数排序。

该任务似乎很难解决：

  • 尽管结果集只有 10 万个标签中的每一个的 10 条记录
  • 保持所有组合的简单算法对内存使用非常敏感：(X,Y) 总共有 0.5*10^12 个组合，它增长为 n^2，其中 n 是标签数

有什么方法可以解决这个问题，而不会将所有组合都保存在内存中或分解为并行算法（类似于 map reduce）来解决？如果我不需要它是 100% 准确的怎么办？

4

2 回答 2

2

我认为在一般情况下，您将无法避免非常糟糕的运行时 - 每个文档中有 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

于 2013-05-16T14:41:33.630 回答
0

我认为即使是最坏的情况也不是你可能担心的坏事。如果有 N 个文档，则有 M 个不同的标签，但每个文档只有 K 个标签。然后一个完整的直方图将有一个硬限制 K*K*N/2 个不同的非零条目（5.5 * 10^10 与您的数字），实际上它会少得多。

顺便说一句：我认为上述观点隐含在 Torrestomp 的回答中，所以除非你对硬限制特别感兴趣，否则你应该接受他的回答。

于 2013-05-16T15:38:55.910 回答