假设我有两个相当大的数据集，第一个称为"Base"，包含2亿个制表符分隔的行，第二个称为为"MatchSet"，包含1000万个相似数据的制表符分隔行。
假设我还有一个名为Match(row1，row2(的任意函数，Match((本质上包含一些启发式方法，用于查看row1(来自MatchSet(并将其与row2(来自Base(进行比较，并确定它们在某些方面是否相似。
假设Match((中实现的规则是自定义的复杂规则，也就是说，不是简单的字符串匹配，涉及一些专有方法。就目前而言，Match(row1，row2(是用psuedo代码编写的，所以用另一种语言实现不是问题(尽管现在是用C++实现的(。
在线性模型中，也就是在一个巨大处理器上运行的程序中，我们会从MatchSet读取每一行，从Base读取每一行都，并使用Match((进行比较，并写出我们的比赛统计数据。例如，我们可以捕获：MatchSet中的X条记录是强匹配，MatchSet中Y条记录是弱匹配，MatchSet中Z条记录不匹配。我们还会将强/弱/非值写入单独的文件中进行检查。Aka，一个嵌套的循环：
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万次迭代。这是最有效的方法吗？
根据您的描述，在我看来，您的问题可能是任意复杂的，可能是维度诅咒的受害者。
例如，假设您的行表示n维向量，并且您的匹配函数是基于基向量和MatchSet向量之间的欧几里得距离的"强"、"弱"或"无匹配"。有很多很好的技术可以在速度、记忆和近似答案的质量之间进行权衡来解决这些问题。至关重要的是，这些技术通常具有已知的时间和空间界限，以及在给定MatchSet原型周围某个距离内找到一个点的概率，所有这些都取决于算法的一些参数。
与其让我在这里漫无边际，不如考虑阅读以下内容：
- 区分位置的哈希
- 当您搜索">位置敏感哈希图reduce"时，Google Scholar上的前几次点击。特别是，我记得我饶有兴趣地阅读了[Das，Abhinandan S.等人的《谷歌新闻个性化：可扩展的在线协作过滤》。第16届万维网国际会议论文集。ACM，2007年
现在，另一方面，如果你能设计出一个直接适用于某种形式的哈希的方案，那么你就可以很容易地用这样的哈希为每个记录生成一个密钥(甚至是少量可能的哈希密钥，其中一个将与查询"基"数据相匹配(，问题就变成了一个简单的大(类似(规模连接。(我说"较大"是因为如果问题确实是连接，那么将200M行与10M行连接起来就相当小了(。例如，考虑CDDB为任何音乐CD CDDB1计算计算32位ID的方式。有时，一个给定的标题可能会产生稍微不同的ID(即，相同标题的不同CD，甚至同一张CD读取多次(。但总的来说，这个标题有一小部分不同的ID。以MatchSet的小型复制为代价，在这种情况下，您可以获得非常快速的搜索结果。
检查论文"数据密集型文本处理"中的Section 3.5 - Relational Joins使用MapReduce。我还没有详细介绍，但它可能会对你有所帮助。
这是一个老问题，但假设您的单流作业进行200M*10M Match((计算，则您提出的解决方案是正确的。通过进行N批(200M/N(*10M的计算，您已经实现了N倍的加速。通过在映射阶段进行计算，然后设置阈值并将结果导向强/弱/无匹配缩减器，可以收集结果以输出到单独的文件中。
如果可以利用额外的优化，他们希望同时应用于单流和并行版本。示例包括阻塞，这样您需要进行少于200M*10M的计算，或者为10M匹配集预计算算法的常量部分。