什么样的数据结构可以用于大量地理坐标中的有效最近邻搜索?使用假定平面坐标的常规空间索引结构,如R-Trees,我看到两个问题(有没有其他人忽视?):
What kind of data structure could be used for an efficient nearest neighbor search in a large set of geo coordinates? With "regular" spatial index structures like R-Trees that assume planar coordinates, I see two problems (Are there others I have overlooked?):
- 绕线和国际日期线
- 极点附近的距离失真
这些因素如何被允许?我猜第二个可以通过改变坐标进行补偿。可以修改R树以考虑到环绕吗?还是有专门的地理空间索引结构?
How can these factors be allowed for? I guess the second one could compensated by transforming the coordinates. Can an R-Tree be modified to take wraparound into account? Or are there specialized geo-spatial index structures?
推荐答案看看 Geohash 。
另外,为了补偿环绕,只需使用一个但三个正交R树,所以地球表面上并没有一点,所以这三棵树在这一点上都有一个环绕。那么,如果根据这些树中的至少一个,它们是接近的两个点。
Also, to compensate for wraparound, simply use not one but three orthogonal R-trees, so that there does not exist a point on the earth surface such that all three trees have a wraparound at that point. Then, two points are close if they are close according to at least one of these trees.
更多推荐
地理坐标的空间索引?
发布评论