c++ - 处理大数据网络文件计算n个最近节点的高效算法

Question

问题:我有两个网络文件(比如 NET1 和 NET2)——每个都有一组节点，每个节点都有唯一的 ID 和地理坐标 X 和 Y。NET2 中的每个节点都有 n 个连接到NET1和n个节点的ID将由最小直线距离决定。输出将包含 NET1、NET2 中节点的三个字段 ID 以及它们之间的距离。所有文件均采用制表符分隔格式。

前进的方向..实现这一点的一种方法是针对 NET2 中的每个节点，我们遍历 NET1 中的每个节点并计算所有 NET1-NET2 距离组合。按 NET2 节点 ID 和距离对其进行排序，并为每个节点写出前四个记录。但问题是 NET1 上有将近 200 万个节点，NET2 上有 2000 个节点——即在该算法的第一步中要计算和写入 40 亿个距离……而且运行时非常令人生畏!

请求:我很好奇你们中是否有人遇到过类似的问题。我很想听听大家关于可用于加速处理的任何算法和数据结构的信息。我知道这个问题的范围非常广泛，但我希望有人能指出正确的方法，因为我在针对这种规模的数据优化代码方面的经验非常有限。

语言:我正在尝试使用 C++、Python 和 R。

请提出想法!帮助非常感谢!

Answer 1

kd-tree是选项之一。它允许您在合理的时间内找到最近的邻居(或一组最近的邻居)。当然，你必须在一开始就构建树，这需要一些时间。但一般来说，kd-tree 是合适的，如果你不必在运行时添加/删除节点，这似乎是你的情况。它还具有较低维度的更好性能(在您的情况下维度为 2)。

另一种可能的数据结构是octree (quadtree 对于 2D)，它是更简单的数据结构(很容易实现)，但是 kd-tree 可以更高效。