假设我有两个相当大的数据集-第一个称为“基础”，它包含2亿个制表符分隔的行，第二个称为“MatchSet”，其中包含1000万个制表符分隔的相似数据行。
假设我还有一个名为Match(row1，row2)的任意函数，并且Match()本质上包含一些启发式方法，用于查看row1(来自MatchSet)并将其与row2(来自Base)进行比较，并确定它们是否在某种程度上相似。
假设Match()中实现的规则是自定义规则和复杂规则，又不是简单的字符串匹配，涉及一些专有方法。假设现在Match(row1，row2)是用伪代码编写的，所以用另一种语言实现不是问题(尽管今天是C++)。
在线性模型中，又名在一个巨型处理器上运行的程序-我们将从MatchSet中读取每一行，从Base中读取每一行，并使用Match()将它们与另一行进行比较，并写出我们的匹配状态。例如，我们可能捕获:来自MatchSet的X记录是强匹配，来自MatchSet的Y记录是弱匹配，来自MatchSet的Z记录不匹配。我们还将强/弱/非值写入单独的文件中进行检查。又称为嵌套循环:
for each row1 in MatchSet
{
for each row2 in Base
{
var type = Match(row1,row2);
switch(type)
{
//do something based on type
}
}
}
我已经开始考虑将Hadoop流式处理作为一种在短时间内作为批处理作业运行这些比较的方法。但是，对于这种类型的问题，我有点难以理解map-reduce范式。
在这一点上，我已经很清楚地理解了如何从hadoop中获取单个输入，如何使用映射函数处理数据，然后发出减少的结果。但是，比较两组记录的“嵌套循环”方法使我有些困惑。
我最接近解决方案的地方是，我仍然仍然必须并行比较2亿条记录中的1000万条记录，因此2亿个/ n节点*每个节点1000万次迭代。那是最有效的方法吗？
最佳答案
根据您的描述，在我看来，您的问题可能会非常复杂，并且可能成为curse of dimensionality的受害者。
例如，假设您的行代表n维 vector ，并且基于基本 vector 和MatchSet vector 之间的欧几里得距离，您的匹配函数是“强”，“弱”或“不匹配”。有许多很好的技术可以在速度，内存和近似答案的质量之间进行权衡来解决这些问题。至关重要的是，这些技术通常伴随着时间和空间的已知界限，以及在给定的MatchSet原型(prototype)周围一定距离内找到一个点的概率，所有这些都取决于算法的某些参数。
而不是让我在这里闲逛，请考虑阅读以下内容:
现在，另一方面，如果您可以设计一种直接适用于某种形式的散列的方案，则可以轻松地为具有这种散列的每个记录生成一个键(甚至是少数可能的散列键，其中一个将匹配查询“基本”数据)，问题就变成了简单的大(-ish)大规模联接。 (我说“比较大”，因为如果问题确实是联接，那么将200M行与1000万行联接起来就很小了)。例如，考虑一下CDDB为任何音乐CD CDDB1 calculation计算32位ID的方式。有时，给定的标题可能会产生略有不同的ID(即，同一标题的不同CD，甚至同一张CD读取了几次)。但总的来说，该标题只有一小部分不同的ID。在那种情况下，以小的MatchSet复制为代价，您可以获得非常快速的搜索结果。