我想知道是否有一种算法可以在O(n)时间内计算最近位置（用经纬度表示）。
我知道可以使用Haversine公式获取参考点到每个位置的距离并按升序排序，但对于大型数据集来说效率低下。
MySQL的DISTANCE()函数执行效率如何？ 我猜是O(n)吗？
10个回答
8
- rampion
1
我该如何使用MySQL实现类似这样的功能？有没有一些好的资源可以帮助我使用kd-tree对经纬度点进行索引和查询？ - mwalsher
2
比O(n)更好？只有采用基数排序或使用哈希键存储位置来表示它们所在的一般位置时才会更好。
例如，您可以使用纬度和经度将地球分成分钟级别的区域，并枚举结果区域，使哈希值成为该位置的区域。因此，在需要查找最近位置时，您只需要检查最多9个哈希键--您可以预先测试相邻网格是否可能提供比迄今为止找到的最佳位置更接近的位置，从而减少计算距离的位置集。它仍然是O(n)，但具有更小的常数因子。如果正确实现，您甚至不会注意到它。
或者，如果数据在内存中或以其他方式随机访问，则可以按纬度和经度排序存储数据。然后，您使用二进制搜索在各自的数据集中查找最接近的纬度和经度。接下来，您继续阅读具有递增纬度或经度（即前面和后面的位置），直到无法找到更接近的位置为止。
当与计算距离的点属于同一经线时，如果按纬度排序的数据的下一个位置的纬度即使属于同一经线也不会比迄今为止找到的最佳情况更接近，则您知道无法找到接近的位置。经度排序数据也适用类似的测试。
这实际上比O(n)更好--接近于O(logN)，但需要随机访问数据，而不是顺序访问，并且需要复制所有数据（或至少是数据的键）。
例如，您可以使用纬度和经度将地球分成分钟级别的区域，并枚举结果区域，使哈希值成为该位置的区域。因此，在需要查找最近位置时，您只需要检查最多9个哈希键--您可以预先测试相邻网格是否可能提供比迄今为止找到的最佳位置更接近的位置，从而减少计算距离的位置集。它仍然是O(n)，但具有更小的常数因子。如果正确实现，您甚至不会注意到它。
或者，如果数据在内存中或以其他方式随机访问，则可以按纬度和经度排序存储数据。然后，您使用二进制搜索在各自的数据集中查找最接近的纬度和经度。接下来，您继续阅读具有递增纬度或经度（即前面和后面的位置），直到无法找到更接近的位置为止。
当与计算距离的点属于同一经线时，如果按纬度排序的数据的下一个位置的纬度即使属于同一经线也不会比迄今为止找到的最佳情况更接近，则您知道无法找到接近的位置。经度排序数据也适用类似的测试。
这实际上比O(n)更好--接近于O(logN)，但需要随机访问数据，而不是顺序访问，并且需要复制所有数据（或至少是数据的键）。
- Daniel C. Sobral
5
任何比O(n)更好的算法都需要随机访问，我不会为此失眠。 - Mark Ransom
或者你可以避免发明自己的算法，使用内置的空间索引支持，或者在最坏情况下使用R-Tree。 - Nick Johnson
嘿，如果你不喜欢我的答案，就不要投票支持它。这里是一个好答案的冒泡排序。话虽如此，R-Tree似乎不适合这个问题。至于空间索引支持，我不知道它的属性，所以我不能保证它。 - Daniel C. Sobral
R-Tree是一种空间索引技术 - 并且它已经在MySQL中以其空间扩展的形式实现。你为什么认为R-Tree不适合呢？ - Nick Johnson
还有其他类型的空间索引。我不知道MySQL选择的属性。无论如何，R-Tree在具体提到的问题上平均水平很高，但最糟糕的情况很差。据说P-R-Tree没有这个问题--实际上，我没有理由怀疑这一点。但是，再次强调，我不知道MySQL正在使用什么。我个人更喜欢kd-tree，并为此投了票。 - Daniel C. Sobral
2
如果要搜索的数据集是静态的，例如美国所有加油站的坐标，则适当的索引（BSP）可以实现高效搜索。Postgres自上世纪90年代中期以来一直对二维索引数据有很好的支持，因此您可以执行此类查询。
- caskey
2
我几年前在DDJ上写了一篇关于寻找最近线路的文章，使用了一个网格（我称之为象限）。将其用于查找最近点（而不是线）只是它的简化版。
使用象限可以大大缩短时间，尽管其复杂度不能在数学上确定（所有点理论上都可能位于单个象限中）。使用象限/网格的先决条件是，您必须有一个要搜索的点的最大距离。如果您只查找最近点而没有给出最大距离，则无法使用象限/网格。
在这种情况下，请看一下最近邻问题的模板（Larry Andrews at DDJ），具有O(log n)的检索复杂度。我没有比较两种算法的运行时间。可能，如果您有合理的最大宽度，象限会更好。更好的通用算法是来自Larry Andrews的算法。
使用象限可以大大缩短时间，尽管其复杂度不能在数学上确定（所有点理论上都可能位于单个象限中）。使用象限/网格的先决条件是，您必须有一个要搜索的点的最大距离。如果您只查找最近点而没有给出最大距离，则无法使用象限/网格。
在这种情况下，请看一下最近邻问题的模板（Larry Andrews at DDJ），具有O(log n)的检索复杂度。我没有比较两种算法的运行时间。可能，如果您有合理的最大宽度，象限会更好。更好的通用算法是来自Larry Andrews的算法。
- RED SOFT ADAIR
1
如果你正在寻找最近的位置，那么无需排序。只需遍历列表，计算到每个点的距离并跟踪最近的点。当你完成遍历后，就会得到答案。
更好的方法是引入网格的概念。您可以将每个点分配给一个网格。然后，在搜索时，首先确定您所在的网格，并对网格中的点执行计算。然而，您需要略微小心。如果测试位置靠近网格边界，则还需要搜索这些网格。尽管如此，这仍然是高性能的解决方案。
更好的方法是引入网格的概念。您可以将每个点分配给一个网格。然后，在搜索时，首先确定您所在的网格，并对网格中的点执行计算。然而，您需要略微小心。如果测试位置靠近网格边界，则还需要搜索这些网格。尽管如此，这仍然是高性能的解决方案。
- George Mastros
3
你给出的算法是O(n)，而不是O(1)。他想要更好的。 - Daniel C. Sobral
然而，“网格”这个概念与另一个答案中提到的哈希表非常接近。 - Michael Todd
我实际上误读了他的回答。不过，第一个是O(n)。 - Daniel C. Sobral
1
我自己没有看过，但Postgres确实有一个专门用于管理GIS数据的模块。
在我以前工作的一个应用程序中，我们将所有数据计算出其四叉树（2D空间）或八叉树（3D空间）的关键字，并将其存储在数据库中。然后，只需从数据库加载值（以防止您重新计算四叉树），并遵循标准的四叉树搜索算法即可。
当然，这意味着您至少会触及所有数据以将其放入数据结构中。但是，持久化此数据结构意味着您可以从那时起获得更好的查找速度。我想您将为每个数据集执行许多最近邻检查。
（对于kd-tree，维基百科有一个很好的解释：http://en.wikipedia.org/wiki/Kd-tree）
- Aidos
0
我想理论上你可以这样做，如果你有足够大的表来完成这个... 其次，也许正确地缓存可以让你得到非常好的平均情况？
- CookieOfFortune
0
可以使用R-Tree索引来加速空间搜索。一旦创建，它允许这样的搜索比O(n)更好。
- Jonathan Leffler
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接