从一组坐标中找出最接近的坐标

我有大约1000套地理坐标(lat,long)。 给定一个坐标,我想find最接近的那个集合。 我的方法是测量距离,但每秒数百个请求可能对服务器执行所有math操作有点粗糙。

什么是最好的优化解决scheme呢?

谢谢

你会想使用“最近邻algorithm” 。

你可以使用这个库sphere-knn ,或者看看PostGIS东西。

为什么不select集合中的潜在最近点(例如,设置一个阈值,比如说0.1,然后过滤集合,以便在目标点的两个轴上都有+ -0.1的点)。 然后在这个集合上做实际的计算。

如果没有一个在第一个范围内,只需放大(0,2)并重复(0.3,0.4 …)直到find一个匹配。 显然你会调整门槛,所以它最好地匹配你的可能的结果。

(我假设时间确定位是实际的距离计算,所以这个想法是限制计算的数量。)

algorithm响应

你的方法已经是O(n)了。 这在algorithm上非常快,而且实现起来相当简单。

如果这还不够,你应该考虑看R树 。 R树背后的想法大致解释如下:

  1. 你已经有了一组n个元素。 您可以对这些数据进行预处理,以形成每个包含一组点的区域的粗略“正方形”,并具有确定的边界。
  2. 现在说一个新的元素出现了,而不是通过每个坐标进行比较,只要比较点是否小于边界就可以确定它属于哪个“平方”, 然后用仅在该平方内的点来测量距离。

你可以立刻看到好处:

  • 您不再与所有坐标进行比较,而只是比较边界(严格小于所有元素的数量),然后与所选边界内的坐标数(也小于所有元素的数量)进行比较。
  • 这种algorithm的上界O(n)时间。 下限可能平均为O(log n)

主要的改进主要是在预处理步骤中(这是“免费”的,因为这是一次性成本),并且减less了所需的比较次数。

系统的回应

只需购买另一台服务器,并使用Haproxy等负载均衡器分发请求和元素。

服务器相当便宜,特别是如果它们对您的业务至关重要,并且如果您想要快速,这是一个简单的扩展方法。