地理坐标的空间索引？

Question

什么样的数据结构可以用于大量地理坐标系中的高效最近邻搜索？有了这样的R-tree“正规”的空间索引结构，即假定平面坐标，我看到两个问题（是否有其他人我都忽略了？）：

• 在两极环绕式和国际日期变更线
• 失真靠近极点的距离

这些因素如何被允许？我想第二个可以通过转换坐标来补偿。可以修改R-Tree以考虑周转吗？还是有专门的地理空间索引结构？

Answer 1

看看Geohash。另外，为了补偿环绕，简单地使用不是一个而是三个正交R树，以便在地球表面上不存在一个点，使得所有三棵树在该点处具有环绕。然后，根据这些树中的至少一个，如果它们靠近，则两个点关闭。

Answer 2

你可以在3个维度使用局部敏感散列（LSH）算法吗？这会很快给你一个近似的邻居组，然后你可以通过计算大圆距离来进行理智检查。

Here's a paper描述用于单元表面上的有效LSH的算法d-维超球面。推测它适用于d = 3。