hadoop - 使用 Hadoop 进行相似性连接

Question

我是 hadoop 的新手。我想和你一起运行一些我想出的方法。

问题:
2 个数据集:A 和 B。
两个数据集都代表歌曲:一些顶级属性、标题 (1..)、表演者 (1..)。
我需要根据标题和表演者使用等式或模糊算法(例如 levenshtein、jaccard、jaro-winkler 等)来匹配这些数据集。
数据集大小为:A=20-30M，B~=1-6M。

所以这里有我想出的方法:

1. 将数据集 B(最小)加载到 HDFS 中。对数据集 A(最大) 使用 mapreduce，其中:
   map阶段:对A中的每条记录访问HDFS，拉取记录B进行匹配；
   reduce 阶段:写入 id 对

2. 以优化的形式将数据集 A 加载到分布式缓存(即 jboss 缓存)中以加快搜索速度。对数据集 B 使用 mapreduce，其中:
   map阶段:对B查询分布式缓存中的每条记录进行匹配
   reduce :写入 id 对

3. 使用 mapreduce 连接两个数据集，其中
   map阶段:从集合A和集合B中获取一条记录，进行匹配
   减少阶段:相同
   (我对此很模糊。第一:加入将是具有万亿条记录的笛卡尔积；第二:不确定 hadoop 如何跨集群并行化它)

4. 使用配置单元(我正在研究如何插入自定义函数来进行字符串匹配)

我正在寻找指示，哪种方法是最佳候选方法，或者可能还有其他一些我看不到的方法。

Answer 1

您可能会发现本文和代码很有用:

Efficient Parallel Set-Similarity Joins Using MapReduce

我在 Cascading 中亲自实现了它取得了良好的效果。不幸的是，该代码过于特定于领域，无法发布。

上述工作的重点是减少连接到很可能相似的候选对的数量，然后可以使用任何相关的混合算法直接比较候选对(在 MR 连接中)。一个好的副作用是可以在集群中均匀地执行此连接，而无需重复比较。

最终，这是对在两个独立集合之间或同一集合内执行交叉连接的优化(第二种情况的实现方式与第一种情况略有不同)。

披露:我是 Cascading 的作者