使用MapReduce编程模型比较两个大型数据集

-1

比方说，我有两个相当大的数据集 - 第一个叫做“Base”，它包含2亿个制表符分隔的行，第二个调用“MatchSet”，它有1000万个标签分隔的相似数据行。让我们假设我也有一个称为Match（row1，row2）的任意函数，Match（）基本上包含了一些针对row1（来自MatchSet）的启发式算法，并将它与row2（来自Base）进行比较，并确定它们是否是在某些方面类似。使用MapReduce编程模型比较两个大型数据集

比方说，在Match（）中实现的规则是自定义和复杂规则，并非简单的字符串匹配，涉及一些专有方法。现在我们假设Match（row1，row2）是用伪代码编写的，所以在另一种语言中的实现不是问题（尽管它今天是在C++中）。

在一个线性模型中，aka程序运行在一个巨大的处理器上 - 我们将从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万条记录比较，因此每个节点有200万/ n个节点* 1000万次迭代。那是最有效的方法吗？

来源

2011-11-28 j03m

我投下了这个问题。首先它不能太启发，因为我们仍然每次看1条记录（至少在上面的描述中）。那么这个问题似乎更多的是理解map-reduce过程，然后调用算法。然后启发式部分实际上是一个算法，这里没有描述。所以可能这个问题应该被重写。 – mariotti

这是肯定的，这是5年前，这可能是真的。我没有编辑（因为我实际上不再关心），我似乎无法删除。 – j03m

检查论文'Data-Intensive Text Processing with MapReduce'中的Section 3.5 - Relational Joins。我没有详细介绍，但它可能会帮助你。

来源

2011-11-28 16:07:15

这是一篇有趣的论文 - 但这里的加入都是基于某个共享密钥的。如果你考虑我的问题，我没有那么奢侈。 – j03m

它在我的阅读列表中。但是，我认为你会觉得很有趣。 –

从您的描述来看，您觉得您的问题可能非常复杂，可能是curse of dimensionality的受害者。想象一下，例如，你的行表示n维向量，并且基于基向量和MatchSet向量之间的欧几里得距离，匹配函数是“强”，“弱”或“不匹配”。在速度，记忆和近似答案的质量之间进行权衡，有很多技术可以解决这些问题。关键的是，这些技术通常具有已知的时间和空间界限，以及在给定的MatchSet原型周围的某个距离内找到一个点的概率，所有这些取决于算法的一些参数。

，而不是我在这里絮叨的话，请考虑阅读以下事项：

Locality Sensitive Hashing
当你搜索“局部性敏感哈希映射精简”在谷歌学术搜索的前几个命中。特别是，我记得阅读[Das，Abhinandan S.等人。 “Google新闻个性化：可扩展的在线协作过滤。”第16届万维网国际会议论文集。ACM，2007]感兴趣。现在

，在另一方面，如果你可以设计一个方案是直接服从于某种形式的散列的，那么你可以很容易地产生了这样一个散列每个记录的键（或者甚至是一小部分可能散列键，其中之一将匹配查询“基本”数据），并且问题变成一个简单的大（ - ）规模连接。（我说“很大”，因为如果问题确实是连接，那么连接10M行的200M行是相当小的）。作为例子，考虑CDDB计算任何音乐CD的32位ID的方式CDDB1 calculation。有时，给定的标题可能会产生稍微不同的ID（即相同标题的不同CD，甚至相同的CD读几次）。但总体而言，该标题有一小组不同的ID。以MatchSet的小型复制为代价，在这种情况下，您可以获得非常快速的搜索结果。

来源

2013-04-10 04:47:03

这是一个古老的问题，但假设您的单流作业执行200M * 10M Match（）计算，您提出的解决方案是正确的。通过进行N批（200M/N）* 10M计算，您已经实现了N倍加速。通过在地图阶段进行计算，然后进行阈值处理并将结果转向强/弱/无匹配缩减器，您可以收集输出结果以分离文件。

如果可以使用其他优化，他们想要应用于单流和并行版本。示例包括阻塞，以便您需要执行少于200M * 10M的计算或预计算10M匹配集的算法常量部分。

来源

2013-09-16 16:19:25

使用MapReduce编程模型比较两个大型数据集

回答

相关问题