我有一个大约2000万坐标的数据集 . 我希望能够以英里为单位传递纬度,经度和距离,并返回在给定坐标的英里范围内的所有坐标 . 我需要响应时间,理想情况下是50毫秒 .
我已经尝试在golang服务中加载内存中的所有坐标,在每次请求时,它将遍历数据并使用hasrsine过滤所有坐标,这些坐标在给定坐标的给定英里距离内 .
此方法在大约2秒内看到结果返回 . 什么方法可以提高结果的速度?我对任何建议持开放态度 .
我正在四处寻找按度数对所有坐标进行分组并且仅按最接近给定坐标进行过滤的想法 . 尽管如此,还没有改善响应时间的运气 . 我的数据集也只是一个测试,因为真实的数据可能会达到数亿 .
3 回答
我认为这更像是一个数据结构问题 . 存储大量地理空间坐标的一种好方法是使用R-tree . 它提供登录M搜索 . 我对Go的知识有限,但是我在一个类似的JS用户应用案例中使用了R-Tree对类似大小的数据集产生了很大的影响 . 从快速搜索看来,似乎至少有一些Go R-Tree实现 .
想法是有一个分隔坐标的“网格”,这样当你需要进行查找时,你可以安全地返回特定单元格中的所有坐标,不要从离目标太远的单元格中返回任何坐标,并且只能执行单元格中坐标的坐标比较,其中包含距离内的一些坐标和距离外的一些坐标 .
简化为1D:
坐标为1到100
你分成5块20
当某人在距离47的距离25内查找所有坐标时,您将返回块[30,39],[40,49],[50,59],[60,69]中的所有坐标,然后对块进行每坐标分析[ 20,29]和[70,79]你另外返回22,23,24,25,26,27,28,29,70,71,72 .
不幸的是,我没有现实的方法来估计这种方法的加速,所以你需要实现它并自己进行基准测试 .
MongoDB具有各种地理搜索$ geoNear将允许您搜索距离点或形状内特定距离内的点 .
https://docs.mongodb.com/manual/reference/operator/aggregation/geoNear/
PostGIS for Postgres有类似的东西,但我对它不太熟悉 .