algorithm - 您如何有效地计算大型重叠组？

Question

我有 2 个非常大的鸟群，它们在 X 英里半径的圆圈中飞行，每个圆圈上都有一个跟踪器，因此我可以确定它们在任何给定时刻的位置。这两个圆圈有一部分重叠(类似于维恩图的样子)。

因为这些是鸟，所以在任何时间点，鸟 A(在圆圈 1 中)可能随机地在或不在重叠区域中。

我想定期计算交叉路口的鸟类并确定它们是哪些鸟类。

我遇到的问题是为此确定正确的数据结构。我考虑过使用 Bloom 过滤器，但它不允许删除(鸟从重叠中移出)并且非常占用内存。

我对任何想法都持开放态度(将数据存储在 Redis 中以供读取等)。

Answer 1

如果圆有固定的中心和半径，当您收到一个位置时，您可以判断该位置是否在重叠范围内(例如，到每个中心的距离是否小于半径)。所以你的问题是维护一个集合，从中删除和插入项目。我首先要尝试的是一个完全普通的数据库，或者一个内存中的 HashSet。

如果 Redis 适合您，那么简单的事情就是在重叠中有一只鸟时创建一个键，在不重叠时将其删除。这允许您测试是否有任何鸟在重叠中，但不能有效地读出其中有哪些鸟。您当然可以在一只鸟被插入并且之前没有进入重叠时增加一个计数器，并在一只鸟移出重叠时减少它，以保持重叠中鸟类的运行计数。

在我看来，您可以使用 Redis 排序集来维护一组重叠的鸟类 - 参见例如ZRANGE，ZADD，ZREM。如果你达到某种限制，你可以为每只鸟存储一个记录，其中包含指向其他鸟类记录的下一个和上一个链接，并在重叠区域构建一个双向链接的鸟类列表 - 使用 Redis 或任何键值您信任的商店。