algorithm - 找到网络上两个有序集合的最小共享值

Question

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

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

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

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

Answer 1

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

这节省了一些数据传输，但需要在两个节点上进行大量处理。