地理座標的空間索引？

Question

什麼樣的數據結構可以用於大量地理座標系中的高效最近鄰搜索？有了這樣的R-tree「正規」的空間索引結構，即假定平面座標，我看到兩個問題（是否有其他人我都忽略了？）：

• 在兩極環繞式和國際日期變更線
• 失真靠近極點的距離

這些因素如何被允許？我想第二個可以通過轉換座標來補償。可以修改R-Tree以考慮週轉嗎？還是有專門的地理空間索引結構？

Answer 1

看看Geohash。另外，爲了補償環繞，簡單地使用不是一個而是三個正交R樹，以便在地球表面上不存在一個點，使得所有三棵樹在該點處具有環繞。然後，根據這些樹中的至少一個，如果它們靠近，則兩個點關閉。

Answer 2

你可以在3個維度使用局部敏感散列（LSH）算法嗎？這會很快給你一個近似的鄰居組，然後你可以通過計算大圓距離來進行理智檢查。

Here's a paper描述用於單元表面上的有效LSH的算法d-維超球面。推測它適用於d = 3。