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

Question

假设我有两个相当大的数据集 - 第一个称为“Base”，它包含 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 万次迭代。这是最有效的方法吗？

Answer 1

根据您的描述，在我看来，您的问题可能非常复杂，并且可能是 curse of dimensionality 的受害者。 .

例如，假设您的行表示 n 维向量，并且您的匹配函数是“强”、“弱”或“不匹配”，基于基向量和 MatchSet 向量之间的欧几里德距离。有很多很好的技术可以通过在速度、内存和近似答案的质量之间进行权衡来解决这些问题。至关重要的是，这些技术通常具有已知的时间和空间界限，以及在给定 MatchSet 原型(prototype)周围一定距离内找到点的概率，所有这些都取决于算法的某些参数。

请考虑阅读以下内容，而不是让我在这里胡说八道:

Locality Sensitive Hashing

当您搜索“ localitysensitive hashing map reduce ”时，Google Scholar 上的前几次点击。特别是，我记得读过 [Das, Abhinandan S., et al. “谷歌新闻个性化:可扩展的在线协同过滤。”第 16 届万维网国际 session 论文集。 ACM，2007] 感兴趣。

现在，另一方面，如果您可以设计一种直接适用于某种形式的散列的方案，那么您可以轻松地为具有这种散列的每条记录生成一个键(甚至是少量可能的散列键，其中一个将匹配查询“基础”数据)，问题就变成了一个简单的大(-ish)规模连接。 (我说“大”是因为如果问题确实是连接，则将 200M 行与 10M 行连接起来非常小)。例如，考虑 CDDB 为任何音乐 CD CDDB1 calculation 计算 32 位 ID 的方式。 .有时，给定的标题可能会产生稍微不同的 ID(即同一标题的不同 CD，甚至同一张 CD 被多次读取)。但总的来说，该标题有一小部分不同的 ID。以 MatchSet 的少量复制为代价，在这种情况下，您可以获得非常快速的搜索结果。