Data structure to perform fast GPS lookups?

Question

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

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

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.

Answer 1

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.

EDIT: 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.