数据结构执行快速GPS查找？ [英] Data structure to perform fast GPS lookups?

问题描述

我有一个带有城市名称和GPS坐标的文本文件（UTF-8，〜50K行）。示例行：

I have a text file (UTF-8, ~50K lines) with city names and GPS coordinates. Example lines:

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坐标。

The third and fourth columns are the GPS coordinates of the cities in the last columns.

给定GPS坐标，我需要找到衣柜城市。我需要这样做数亿次。什么是一些可以帮助我完成这项任务的工具？ Java / Python解决方案将是理想的。

Given a GPS coordinate, I need to find the closet city. I need to do this hundreds of millions of times. What are some tools that can help me with this task? Java/Python solutions would be ideal.

推荐答案

您正在寻找的是一个 =noreferrer> KD树。我在这里找到了一个 python实施的链接，但我不是python开发人员，从来没有尝试过。 KD树将支持寻找平面中最近点的平方根复杂度，这可能是您可以获得的最佳复杂度。您可以承受一秒钟的大概一百万次查询。

What you are looking for is a KD tree. I found a link to a python implementation for it here, but I am not python developer, never tried it. The KD tree will support for square root complexity of finding the nearest point in a plane, which is maybe the best complexity you can get. You can afford making probably about a million queries a second.

编辑：其实你的问题让我做了更多的研究。您可能会发现此页面中描述的可行方法。您最感兴趣的是为最近邻居的许多查询提供最佳解决方案。

Actually your question made me make a bit more thorough research. Probably you will find useful what is described as possible approaches on this page. What you are interested in is providing optimal solution for many queries of nearest neighbour.

这篇关于数据结构执行快速GPS查找？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！