我有以下任务：
有1000万份文件
有10万个独特的标签
每个文档有100个标签
对于每个标签X，我需要找到10个顶级Y标签，其中X和Y都存在于文档中，按X和Y都存在的文档数排序。
这项任务似乎相当复杂，难以解决：
尽管结果集对于每个100k标签只有10条记录
保持所有组合不变的直接算法对内存使用非常敏感：总共有0.5*10^12个（X，Y）组合，并且随着n^2而增长，其中n是标签的数量
有没有什么方法可以解决这个问题，而不需要将所有的组合都保存在内存中，或者使用并行算法（类似于map reduce）来解决？如果我不需要百分之百准确呢？
最佳答案
我认为在一般情况下，您将无法避免非常糟糕的运行时-每个文档中有5050对，和10M个文档，所有组合似乎都是可能的。
然而，在典型的真实数据中，您很少需要处理“敌对”输入。一个可能的解决方案是首先计算所有10万个术语的出现次数，对它们进行排序，然后对每个术语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时删除最弱的元素。
b）假设您正在确定前10对X&Y，其中X=“大象”假设在扫描1000个y项之后，有一个大小为10的堆，其中最小得分对的计数为300。现在假设您检查的第1001个术语有doc count 299—因为只有299个文档有Y术语，所以最多299个文档也有X&Y，因此它不可能比您目前拥有的前10对中的任何一对更好，而且由于所有Y术语都是按doc频率排序的，事实上您现在知道您不必再检查任何一对了这就是max语句向您保证的。
c）您为每个X所做的选择纯粹是一个优化决策如果你有很多X，它只存在于少量的文件中，这是一个很好的问题，这意味着每学期的工作更少。
d）如果你能忍受前10名出错的非零概率（每个学期），你可能可以通过使用抽样方法而不是对索引进行全面、严格的扫描来减少运行时的错误术语X在文档索引中越流行，在根据收集到的信息获得正确的前10对X&Y之前，您需要扫描的文档（按比例）就越少要想得出这方面的确切数字，就需要对基础指数中术语的预期分布有所了解特别是：术语之间有多大关联？数字n（x）/MAXY（x）一般是什么样子的，其中n（x）是具有x项的文档数，而MAXY（x）是与x x y相关的文档的数量，在所有条件y上最大化。=x个
关于algorithm - 有序组合算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16589245/