设计 MapReduce 函数以查找集合列表之间的交集

Question

假设我有多个列表

L1 = [{2,7},{2,7,8},{2,3,6,7},{1,2,4,5,7}]      
L2 = [{3,6},{1,3,4,6,7},{2,3,5,6,8}]      
L3 = [{2,5,7,8},{1,2,3,5,7,8}, {2,4,5,6,7,8}]

L1、L2、L3各元素的交集为：

{2,7}.intersection({3,6}).intersection({2,5,7,8})= empty  
{2,7}.intersection({3,6}).intersection({1,2,3,5,7,8})= empty  
{2,7}.intersection({3,6}).intersection({2,4,5,6,7,8})= empty  
{2,7}.intersection({1,3,4,6,7}).intersection({2,5,7,8})= {7}  
{2,7}.intersection({1,3,4,6,7}).intersection({1,2,3,5,7,8})= {7}  
{2,7}.intersection({1,3,4,6,7}).intersection({2,4,5,6,7,8})= {7}
...............................

如果我们继续这样做，我们最终会得到以下集合：

{{empty},{2},{3},{6},{7},{2,3},{2,5},{2,6},{2,8},{3,7},{4,7},{6,7},{1,7}}

假设我有很多列表 L1、L2、L3、...Ln。我如何设计 Map 和 Reduce 函数来计算这些输入列表集之间的交集。

请帮忙。我只需要想法。

Answer 1

这不可能适合单个 Map/Reduce 工作。我真的不认为这个用例一般来说非常适合 M/R 范例，因为它似乎不能很好地并行化并且涉及大量数据要洗牌。

为了简单起见，我将把输入和运算符翻译成更简单的版本，保持它们的属性不变。假设您有数字列表和总和列表，而不是集合列表和交集列表（为了我们的目的，这应该是等价的）。

所以您想计算从不同列表中选择的所有可能的数字总和：

输入：

L1: [1, 2, 3]
L2: [4, 5]
L3: [6, 7]

结果：

[
  1+4+6, 1+4+7, 1+5+6, 1+5+7,
  2+4+6, 2+4+7, 2+5+6, 2+5+7,
  3+4+6, 3+4+7, 3+5+6, 3+5+7
]
 = [11, 12, 12, 13, 12, 13, 13, 14, 13, 14, 14, 15]

删除重复项后，您将得到：

[11, 12, 13, 14, 15]

检查点：请确认我的要求是否正确。

为了最终计算 reducer 中的总和，每个列表中的每个元素都需要从 mapper 输出，其键数等于所有其他列表的长度相乘；并且键需要允许加入减速器中不同列表的所有元素组合。

由于列表不一定具有相同的大小，因此只有在评估每个列表记录时知道数据集中每个其他列表的确切长度，才能确保上述内容。（此先验知识意味着另一个 M/R 作业来生成长度数组。）然后，您可以通过连接每个可能的元素索引组合来计算键。

在我们的示例中，值“1”（L1 中的索引 0）将在以下键下发出："000"（即 1+4+6）、"001" , "010", "011"（探索从“1”到其余列表的所有可能路径）。对于值“7”（L3 中的索引 1），我们将有："001"、"011"、"101"、"111"、"201"、"211".

一旦你这样做了，你最终会在 reducer 中得到要在同一个键下求和的数字（这正是你想要的，除了你在这个阶段仍然有重复的和）：

"000" -> [1, 4, 6]
"001" -> [1, 4, 7]
...
"211" -> [3, 5, 7]

但是要洗牌的数据相当多！当然，您也可以将 reducer 用作组合器，但仍然：对于大小为 M 的 N 个列表，您将在每个列表中发出 M^N 次元素。我假设 N 以百万为单位（至少），否则你不会考虑 map/reduce。此外，您从 map 输出的每个键都是一个长度为 N（数据集中列表的数量）的字符串。所以你很容易得到 MB 大小的密钥（即使你切换到更紧凑的二进制格式）。

为此，您需要一个计算列表大小数组的先决条件作业，最后，重复数据删除可能还需要另一个作业（除非您正在写入某个存储，它会为您执行此操作).

总而言之，一定有更好的方法... 如果您的数据集适合单个节点的内存，请尝试一下。您正在计算的交集会自然缩小，并且（如果幸运的话）其中大部分很快就会变成空集。

设计 MapReduce 函数以查找集合列表之间的交集

Design MapReduce function to find intersection sets between list of sets

hadoop

mapreduce

set