On Wed, Mar 19, 2014 at 4:57 PM, S. Dale Morrey <[email protected]> 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 /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
