Page 1 of 1

Matching closest long/lat

Posted: Sat Feb 12, 2011 1:34 pm
by John Cartwright
Using Maxmind's GeoIP software, we can narrow down the LONG/LAT to relative accuracy within 25 miles around 80% of the time.

Now, we don't want to use any of the other information provided by MaxMind, because there are a lot of discrepancies between feature names, i.e., cities, to perform a look up. We plan on attempting such a look up if other methods fail to locate a feature, but for performance reasons, look ups on floats are much faster than strings.

Now, I'm a little clueless on how we can find the closest matching LAT/LONG given from Maxmind to our database. The problem is, our datbase features has a much higher precision compared to that of Maxmind, therefore a straight comparison might not be effective. If we try applying a ROUND() to the column during query, that will obviously be really slow.

Given the following data, would the fastest way simply be something like

LAT 79.93213
LONG 39.13111

SELECT `feature_name` FROM `geo_features`
WHERE long BETWEEN 79.93213 AND 79.79.93214
AND last BETWEEN 39.13111 AND 39.13112

Can anyone thing of an elegant solution that will be blazing fast? I know there are some new spatial storage types in MySQL 5, perhaps anyone can provide a solution beyond the blinders I've seem to put up on myself.

Re: Matching closest long/lat

Posted: Mon Feb 14, 2011 10:32 am
by pickle
I wrote a little script for my church that - given a user provided street address, returns all the churches in our Synod in order of proximity. There's an SQL query floating around the interwebs that uses a bunch of spherical geometry to find the closest co-ordinates to a set of initial coordinates. I can't speak to the speed of it though - my table only has a couple dozen entries so speed isn't really an issue.

I can dig out the code for that if you'd like.

Re: Matching closest long/lat

Posted: Mon Feb 14, 2011 11:09 am
by John Cartwright
It certainly would be worth looking at, but I think I can safely assume any trigonometry operation will probably be quite slow since the look up table is ~3M rows.

I think my only two possible alternatives are to

1) Create a secondary cache table populated from only the most likely cities, which would result probably in a table no more than 30k rows
2) Use MySQL spatial extension

I realize this morning that none of the columns are indexed because of the size of the table. Therefore, a cache table and perhaps using spatial extensions on top of that would be the best candidate.

Re: Matching closest long/lat

Posted: Mon Feb 14, 2011 11:31 am
by pickle
A stored procedure might help too.

This is the site that had the query I modified: http://blog.peoplesdns.com/archives/24

Here's a thread/post on the MySQL forums about a zip code proximity search - which might be analogous to what you want to do: http://forums.mysql.com/read.php?23,3868,50571

Re: Matching closest long/lat

Posted: Mon Feb 14, 2011 11:42 am
by John Cartwright
Thanks for the links. I will let you know how it goes.