用于执行快速GPS查找的数据结构？

Question

我有一个带有城市名称和GPS坐标的文本文件(UTF-8,~50K行).示例行:

San Pedro    locality   -3367   -5968   Argentina       Buenos Aires    San Pedro
Talagante    locality   -3366   -7093   Chile   Metropolitana   Talagante
Peñaflor     locality   -3362   -7092   Chile   Metropolitana   Talagante

第三和第四列是最后一列中城市的GPS坐标.

给定GPS坐标,我需要找到壁橱城市.我需要做数亿次这样的事情.有哪些工具可以帮助我完成这项任务？Java/Python解决方案将是理想的选择.

Answer 1

你在寻找的是一棵KD树.我在这里找到了一个python实现的链接,但我不是python开发人员,从未尝试过.KD树将支持在平面中找到最近点的平方根复杂度,这可能是您可以获得的最佳复杂度.您可以承受每秒大约一百万次查询.

编辑:其实你的问题让我做了一些更彻底的研究.您可能会发现本页描述的可能方法很有用.您感兴趣的是为最近邻居的许多查询提供最佳解决方案.