优化Python KD树搜索

Question

Scipy(http://www.scipy.org/)提供两个KD Tree类; KDTree和cKDTree.

cKDTree要快得多,但是比KDTree更少可定制和查询(据我从文档中可以看出).

这是我的问题: 我有一个3百万二维(X,Y)点的列表.我需要从每个点返回X单位距离内的所有点.

使用KDtree,有一个选项可以做到这一点:KDtree.query_ball_tree()它生成一个列表,其中包含每个其他点的X个单位内的所有点.但是:这个列表很庞大,很快就会填满我的虚拟内存(大约7.44亿个项目).

潜在的解决方案#1:有没有办法在写入时将此列表解析为文本文件？

潜在的解决方案#2:我尝试使用for循环(对于列表中的每个点),然后通过使用:找到X单位内的单点邻居KDtree.query_ball_point().但是:这需要永远,因为它需要运行数百万次查询.是否有与此KDTree工具相当的cKDTree？

潜在的解决方案#3:打败我,其他人有什么想法？

Answer 1

从 scipy 0.12 开始，两个 KD Tree 类都具有功能奇偶校验。引用其公告：

cKDTree 功能完整

KDTree 的 Cython 版本 cKDTree 现已功能完整。cKDTree 中的大多数操作（构造、查询、query_ball_point、query_pairs、count_neighbors 和稀疏距离矩阵）比 KDTree 快 200 到 1000 倍。需要注意的是，cKDTree 具有与 KDTree 完全相同的接口，并且可以用作直接替代品。