存储距离敏感空间数据的最佳数据结构是什么？

Question

假设我有全球气象站坐标​​、历史温度值和市中心坐标的数据。气象站位于距市中心不同的距离。任务是根据气象站的数据确定城市温度的​​历史平均值。

为了解决每个城市的问题，我需要在某个半径内找到一组最近的气象站并对它们的数据进行平均。蛮力的方法是计算从每个城市到每个气象站的距离，但它对我的数据来说太慢了。所以我认为一些树数据结构可以在这里提供帮助。我尝试使用 R-trees 按坐标划分气象站，但存在一个问题 - 这种方法允许我在某些树节点中找到气象站，但它没有给我关于相邻节点的信息，以快速计算半径条件（例如，如果城市非常靠近 R 树节点的边界）。

是否有一个标准的树数据结构可以快速搜索所需节点，同时提供同一树级别的空间邻居集？

Answer 1

使用数据库怎么样？然后查询它以找到接近某个特定点的点？许多数据库已经支持地理空间数据，您可以对其进行索引和查询：

• posgis
• mongodb geospatial
• mysql extension

Answer 2

你可能不应该关心 'neighbours on same level' 之类的，这些信息并不一定意味着什么。我想你应该

1. 决定是要给定距离内的所有气象站（范围查询）还是最近的k个气象站。
2. 然后我将使用您正在使用的索引的 API 来查找电台。
3. 然后计算距离。

R-Trees 可以，但加载速度通常很慢。如果加载时间有问题，您可能想尝试 R+tree、R*tree 或者四叉树（对于小数据集）或 PH-Tree（对于大数据集，我在 Java 中的实现）。

数据在树中的组织方式应该不是问题。实施这棵树的人可能实施了寻找所需邻居的最有效方法。