algorithm - Spark : Find pairs having at least n common attributes?

Question

我有一个由(sensor_id, timestamp, data) 组成的数据集(sensor_id 是物联网设备的ID，时间戳是UNIX 时间，数据是他们当时的输出)。表上没有主键，但每一行都是唯一的。

我需要找到所有对 sensor_id s1 和 s2 使得这两个传感器至少有 n (n=50) 个条目 (timestamp, data) 在它们之间是共同的，即在 n 不同的场合，它们在相同的时间戳发出相同的数据.

为了了解数据量级，我有 10B 行和约 5000 万个不同的 sensor_ids，我相信大约有约 500 万对传感器 ID 在同一时间戳发出相同数据至少 50 次。

在 Spark 中执行此操作的最佳方法是什么？我尝试了各种方法(按 (timestamp, data) 分组和/或自连接)，但它们的复杂性非常昂贵。

Answer 1

这是一个伪代码，从 Spark 中抽象出来。您可以先对数据集进行排序:

select id, timestamp, data order by timestamp, data, id

示例 10 行:

s1,100,a  #1
s2,100,a  #2
s3,100,a  #3
s4,100,b  #4
s1,101,a  #5
s3,101,b  #6
s4,101,b  #7
s2,101,a  #8
s3,102,b  #9
s4,102,b  #10

现在从上到下迭代，只要时间戳和数据与上一个条目相同，就构建一个条目列表。

在我们的示例中，第 1-3 行构成了这样一个列表，因此我们已经看到了一些潜在的对:

s1, s2
s1, s3
s2, s3

第 4 行只是带有 (100,b) 的单个条目，我们可以跳过它。第 5 行只有一个带有 (101,a) 的条目，我们可以跳过它。

第 6 行和第 7 行是新的一对:

s3, s4

#9 和#10 也是一对

将它们放在一起可以很容易地数出对数:

s1, s2
s1, s3
s2, s3
s3, s4
s3, s4

这种方法的好处是，如果你可以对文件进行排序，你可以将排序后的数据集分成多个较小的 block ( block 应该在组边界上分割——即#1、2、3 应该在一个 block 中) ，计算对，并加入最终结果作为最后一步。

希望对您有所帮助。