Optimum search with geospatial coordinates

Levi Pearson levipearson at gmail.com
Wed Mar 19 17:42:02 MDT 2014


On Wed, Mar 19, 2014 at 4:57 PM, S. Dale Morrey <sdalemorrey at gmail.com> wrote:
> Agreed, an rtree was not what I was balking about and loading into an rtree
> is an expensive one time process but it can be serialized to the device
> storage for quick loading.
>
> I was balking at using a full on database solution :D
> Although I did just find out that the device OS uses SQLite for preferences
> storage, so maybe there is room for a DB in there.
>
> FYI this is just a RAD app that, like you mentioned is a list of stores and
> we want to hit the user with the closest store when they open the app.
> Imagine pressing a button on your phone and being presented with the
> nearest gas station to your current location already loaded into GPS &
> nav.  That's pretty close to what I'm trying to achieve here.

Unless there's some massive number of stores in the data set, the
asymptotics probably aren't going to matter all that much to your
usability case. Load up a sample set and see how the naive search
works.  If it's good enough, it's good enough.

But because it's really interesing, I'll point out this technique for
sorting/linearizing a multi-dimensional data set into a single
dimension while preserving locality:
http://en.wikipedia.org/wiki/Z-order_curve

If you look down to the section on "Use with one-dimensional data
structures for range searching" you should be able to use that
algorithm to cut down the portion of the array you need to walk
through to find the nearest points.  Here's a direct link to the
referenced paper that describes the algorithm in detail:
http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf

    --Levi


More information about the PLUG mailing list