go - 按距离快速搜索数百万个坐标

Question

我有一个大约有 2000 万个坐标的数据集。我希望能够传入以英里为单位的纬度、经度和距离，并返回在给定坐标的英里范围内的所有坐标。我需要将响应时间理想地控制在 50 毫秒以下。

我已经尝试将所有坐标加载到 golang 服务的内存中，该服务根据每个请求循环遍历数据并使用 haversine 过滤所有在我给定坐标的给定英里距离内的坐标。

此方法会在大约 2 秒内返回结果。什么方法可以提高结果的速度？我愿意接受任何建议。

我正在考虑按度数对所有坐标进行分组并仅过滤最接近给定坐标的想法。尽管如此，还没有改善响应时间的运气。我的数据集也只是一个测试集，因为真实数据可能有数亿。

Answer 1

我认为这更像是一个数据结构问题。存储大量地理空间坐标的一种好方法是使用 R-tree .它提供 log_n M 搜索。我对 Go 的了解有限，但我在 JS 应用程序的类似用例中使用 R-Tree 对类似大小的数据集产生了很好的效果。通过快速搜索，似乎至少有几个 Go R-Tree 实现。