1

周期性地，应用程序将接收大量具有纬度和经度的移动物体（每秒大约 100,00,000 [100 万] 个）。要求是检测 400 米距离内的任何物体，检测必须在 400 毫秒（毫秒）内完成。

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

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

选项 2：使用八叉树数据结构，这将提供更好的性能由新对象。

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

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

考虑到未来物体可以达到每秒 200 万个，任何人都可以提出一种不同的方法吗？

4

1 回答 1

0

两点：

1）分区时，可以让象限重叠，即一个象限边界400m内的所有点都相加两个象限。我认为这应该允许有用的分区。

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

于 2015-11-24T22:27:40.967 回答