how to sort geographical data for quick search

Question

I have some objects that are geo-localized (I have for each object the latitude + longitude). My App needs to display the objects that are 3 kilometers around the GPS position of the mobile device. I have several thousands of objects and they are localized in large area (for example, several US state, several small country), meaning in my list of objects I can have one located in NYC and another one in Miami but I can have also objects that are very close (few meters).

Currently, my App performs an iterative search. For each objects I compute the distance with the GPS position and if distance is <= 3KM then I keep the object else I ignore it. This algorithm is not very efficient and I'm looking for an Algorithm that will give better performance.

I suppose there's a way to sort my objects using the geo coord and next to find more quickly the objects that are located around the GPS position.

My current idea is just to compute rectangle with the "extreme points", North / South / East / West (from 3km of the GPS position) to limit the search zone. Next I will compute the distance only for the objects inside this box. I think something better could be done but I don't have the idea...

Any proposal will be appreciated ;-) Thanks,

Séb.

Answer 1

Sounds like a nearest neighbor search, but not with a maximum number of neighbors (as in kNN), but with a maximum distance threshold.

A common approach is to put the objects into a special data structure to allow ruling out large parts of the search space fast. However, these are usually made with euclidean spaces in mind, and not for the spherical (lat/lon-)plane (wrap-around issues). Therefore, you'd probably need to convert your coordinates to 3d coordinates in a cartesian system relative to the center of the sphere before you can apply one of the following data structures to search efficiently for your objects:

• Octree
• kd-tree