查找网络上两个排序集的最小共享值

Question

我有两个节点通过网络连接。它们每个都有一组排序的值(在本例中为整数(。

我想找到两组交集的最小值。由于延迟和带宽限制，将一个集传输到另一个节点并在本地执行操作是不可行的。

有没有办法在尽可能少的步骤中找到不需要 O(N( 数据传输的交集的最小值？

编辑：这些集可能很稀疏。集合 A 的最小值可能不存在于集合 B 中。

Answer 1

一种方法是在一个节点上创建一个布隆过滤器，将其发送到另一个节点，从本地最小值开始运行双向搜索。

这样可以节省一些数据传输，但需要在两个节点上进行相当数量的处理。