最近的邻居搜索1到200万移动对象

Question

定期地，应用程序将会接收到大量移动对象（大约每秒100,00,000 [100万]）的经度和纬度。 要求是检测400米范围内的任何物体，检测必须在400毫秒（毫秒）内完成。

因此，每当应用程序接收到具有经度和纬度的任何新对象时，我首先需要将其添加到数据结构中，并检查数据结构中的任何其他对象是否与400中新添加的对象的距离不超过400米女士。

从我的研究，我有以下2个选项： 选项1： Redis的GEO可以用于上述规定，如果对象的数量较少。但是，对于执行geoadd和georadius查询的一百万个对象将花费超过400毫秒，这是不可接受的。将来这些对象可能是每秒200万。

选项2：使用八叉树数据结构的，这将提供更好的性能，我认为它的性能也将降低，同时更新与新对象八叉树（将需要超过400毫秒的时间更长） 100万的对象和搜索新对象附近的对象。

我认为很多关于使用geohash分区数据。示例使用geohash的前缀并将数据保存在redis实例1中，并将其他数据保存在redis实例2中。但是，对于两个对象在400 m范围内但在相邻象限内的情况，将失败。

问题 有没有人有任何想法根据经纬度划分数据，仍然检测邻近的物体？或者减少地图缩小范式中的问题？

任何人都可以提出一种不同的方法，考虑到将来的对象可能是每秒200万？

Answer 1

两点：

1）分区，可以让象限重叠，这意味着内象限边界400米的所有点都增加了两个两个象限。我认为这应该允许有用的分区。

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