redis - 最近邻搜索 1 到 200 万个移动物体

Question

应用程序会定期接收大量带有纬度和经度的移动对象(每秒大约 100,00,000 [100 万])。要求是检测400米距离内的任何物体，检测必须在400 ms(毫秒)内完成。

因此，每当应用程序收到任何带有纬度和经度的新对象时，我首先需要将其添加到数据结构中，然后检查数据结构中的任何其他对象是否在 400 毫秒内距离新添加的对象 400 米以内。

根据我的研究，我有以下两种选择:选项1:如果对象数量较少，可以使用Redis GEO 来满足上述需求。但是，对于 100 万个对象，执行 geoadd 和 georadius 查询将花费超过 400 毫秒，这是 Not Acceptable 。 future 对象可以达到每秒 200 万个。

选项 2: 使用 Octree 数据结构可以提供更好的性能我认为它的性能也会降低(需要比 400 毫秒更长的时间)对于 100 万个对象，同时用新对象更新八叉树并搜索新对象附近的对象。

我想了很多关于使用 geohash 对数据进行分区的问题。示例 使用 geohash 前缀，将数据保存在 redis 实例 1 中，将其他 geohas 数据保存在 redis 实例 2 中。但是对于极端情况，当两个对象在 400 m 范围内但在相邻象限中时，它将失败。

问题有没有人知道根据纬度和经度对数据进行分区并仍然检测相邻物体？或者减少 map-reduce 范式中的问题？

考虑到将来对象可以达到每秒 200 万个，有人可以提出不同的方法吗？

Answer 1

两点:

1) 对于分区，您可以让象限重叠，这意味着象限边界 400m 以内的所有点都被添加到两个象限中。我认为这应该允许有用的分区。

2) 有专门用于移动对象的索引，这可能比四叉树更好，例如 MX-CIF-Quadtree。您也可以尝试我自己的 PH-Tree ( Java sources )。它可以很好地适应大型数据集(最好使用至少 10^6 个点)并且具有良好的更新性能。它实际上最适合集群数据。它基本上是一个具有大量优化的前缀共享四叉树(例如，它从不需要重新平衡)。在 3.5GHz 的 i7 3770K 上，我每秒可以插入 500K 到 1M 点，树大小高达 100M(我当时停止了测试，但树应该可以轻松扩展到更大的数据集)。