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

Question

考虑我拥有全球气象站坐标、历史温度值和城市中心坐标的数据。气象站与城市中心之间的距离不同。任务是通过气象站的数据确定城市温度的平均历史值。

要解决这个问题，我需要找到每个城市在某个半径内最近的气象站集，并对其数据求平均值。暴力计算每个城市到每个气象站的距离的方法对我的数据来说太慢了。因此，我想使用一些树形数据结构来帮助解决问题。我尝试使用 R 树按坐标划分气象站，但存在一个问题——这种方法只允许我查找某个树节点中的气象站，无法提供相邻节点的信息，以便快速计算半径条件（例如当城市非常靠近 R 树节点边界时）。

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

- Kivan

---

R树确实允许半径搜索和最近邻搜索，因此它应该是一个很好的选择。 - Has QUIT--Anony-Mousse

Answer 1

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

- PostGIS - MongoDB 地理空间 - MySQL 扩展

- Salvador Dali

---

根据文档所示，索引也是基于R树的，因此似乎数据库会遇到与我相同的问题。 - Kivan

@user3231055，你的陈述看起来相当有趣。很可能是你做错了什么或者没有正确实现R-Tree，也可能是你没有正确使用数据。因为这些数据库已经使用了多年，没有多少人声称他们遇到了问题。 - Salvador Dali

Answer 2

您可能不需要担心“同一级别的邻居”之类的内容，这些信息并不一定意味着太多。我认为您应该：

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

R树对此来说还可以，但它们通常加载速度相当慢。如果加载时间是一个问题，您可能需要尝试R+tree、R*tree，或者也许四叉树（适用于小数据集）或PH-Tree（适用于大数据集，我的Java实现）。

树中数据的组织方式不应成为问题。无论谁实现了树，都可能实现了找到所需邻居的最有效方法。

- TilmannZ