我想知道是否有一种算法可以比 O(n) 时间更好地计算最近的位置（由纬度/经度表示）。
我知道我可以使用 Haversine 公式来获取从参考点到每个位置的距离并对 ASC 进行排序，但这对于大型数据集来说效率低下。
MySQL DISTANCE() 函数如何执行？我猜O（n）？
问问题
3463 次
10 回答
8
If you use a kd-tree to store your points, you can do this in O(log n) time (expected) or O(sqrt(n)) worst case.
于 2009-07-29T03:35:05.630 回答
2
If the data set being searched is static, e.g., the coordinates of all gas stations in the US, then a proper index (BSP) would allow for efficient searching. Postgres has had good support since the mid 90's for 2-dimensional indexed data so you can do just this sort of query.
于 2009-07-29T03:34:09.127 回答
2
几年前，我使用网格（我称之为象限）写了一篇关于在 DDJ找到最近线的文章。使用它来查找最近的点（而不是线）只是减少它。
使用象限可以大大减少时间，尽管复杂性在数学上无法确定（理论上所有点都可以位于一个象限中）。使用象限/网格的先决条件是，您有一个搜索点的最大距离。如果您只是寻找最近的点，而不给出最大距离，则不能使用象限。
在这种情况下，请查看最近邻问题的模板（DDJ 的 Larry Andrews），其检索复杂度为 O(log n)。我没有比较两种算法的运行时间。可能，如果你有一个合理的最大宽度，象限会更好。更好的通用算法是来自 Larry Andrews 的算法。
于 2009-07-29T08:55:27.683 回答
2
比 O(n) 更好？仅当您采用基数排序方式或使用表示它们所在的一般位置的哈希键存储位置时。
例如，您可以用经纬度将地球划分为分钟，枚举结果区域，并将某个位置的哈希值设为其区域。因此，当需要获取最近的位置时，您最多只需要检查 9 个哈希键 - 您可以预先测试相邻网格是否可能提供比目前找到的最佳位置更接近的位置，从而减少位置集计算到的距离。它仍然是 O(n)，但常数因子要小得多。正确实施你甚至不会注意到它。
或者，如果数据在内存中或以其他方式随机访问，您可以按纬度和经度排序存储它。然后，您可以使用二进制搜索来查找相应数据集中最接近的纬度和经度。接下来，您继续阅读纬度或经度增加的位置（即前面和后面的位置），直到无法找到更近的位置。
您知道，当纬度排序数据任一侧的下一个位置的纬度不会比迄今为止发现的最佳情况更接近时，即使它们与该点属于同一经度，您也找不到接近的位置正在计算哪个距离。类似的测试适用于经度排序的数据。
这实际上比 O(n) 更好——我认为更接近 O(logN)，但确实需要随机而不是顺序访问数据，以及复制所有数据（或数据的键，至少）。
于 2009-07-29T03:09:19.737 回答
1
你需要一个空间索引。幸运的是，MySQL 在其Spatial Extensions中提供了这样的索引。他们在内部使用 R-Tree 索引——尽管他们使用什么并不重要。上面引用的手册页有很多细节。
于 2009-07-29T08:29:27.767 回答
1
我自己没有看过，但是 Postgres 确实有一个专门用于管理 GIS 数据的模块。
在我前世工作的一个应用程序中，我们获取了所有数据，计算出它是四叉树（用于 2D 空间）或八叉树（用于 3D 空间）的键，并将其存储在数据库中。然后从数据库中加载值（以防止您必须重新计算四叉树）并遵循标准四叉树搜索算法是一件简单的事情。
这当然意味着您将至少触摸所有数据一次以将其放入数据结构中。但是保持这种数据结构意味着您可以从那时起获得更好的查找速度。我想你会为每个数据集做很多最近邻检查。
（对于 kd-tree 的维基百科有一个很好的解释：http ://en.wikipedia.org/wiki/Kd-tree ）
于 2009-07-29T04:24:08.727 回答
1
如果您正在寻找 (1) 最近的位置，则无需排序。只需遍历您的列表，计算到每个点的距离并跟踪最近的点。当你通过列表时，你会得到你的答案。
更好的是引入网格的概念。您可以将每个点分配给一个网格。然后，对于您的搜索，首先确定您所在的网格并对网格中的点执行计算。不过，你需要小心一点。如果测试位置靠近网格边界，您还需要搜索这些网格。不过，这可能是高性能的。
于 2009-07-29T03:14:20.943 回答
0
R-Tree 索引可用于加速这样的空间搜索。一旦创建，它允许这样的搜索比 O(n) 更好。
于 2009-07-29T03:52:05.970 回答
0
我想如果您有足够大的表来执行此操作，理论上您可以做到这一点......其次，也许正确缓存可以让您获得非常好的平均情况？
于 2009-07-29T03:10:17.503 回答