地理坐标的空间索引？

Question

8

什么样的数据结构可以用于在大量地理坐标中进行高效的最近邻搜索？对于像R-Tree这样假定平面坐标的“常规”空间索引结构，我看到了两个问题（我有没有忽略其他问题？）：

- 在极点和国际日期变更线处的环绕 - 在极点附近距离的扭曲

如何考虑这些因素？我猜第二个问题可以通过转换坐标来补偿。是否可以修改R-Tree以考虑环绕？还是有专门的地理空间索引结构？

- Michael Borgwardt

2个回答

2

请看Geohash。

此外，为了弥补环绕问题，只需使用三个正交的R树，这样就不存在一个点在地球表面上，使得这三棵树都在这一点处发生环绕。然后，如果两个点在至少一个树中是接近的，则它们是接近的。

- jkff

Geohash似乎是一种“大部分时间都能很好地工作”的东西，但不能依赖它总是为附近位置提供一个共同的前缀。然而，使用多个R树来解决环绕问题的想法看起来是一个不错的解决方案。 - Michael Borgwardt

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Josh McFadden · Accepted Answer

你能在三维空间中使用局部敏感哈希（LSH）算法吗？这将快速为您提供一个近似的相邻组，然后通过计算大圆距离进行合理性检查。

这篇论文描述了一种在单位d维超球面上高效LSH的算法。据推测，它适用于d=3。