Matching closest long/lat

Questions about the MySQL, PostgreSQL, and most other databases, as well as using it with PHP can be asked here.

Moderator: General Moderators

Post Reply
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Matching closest long/lat

Post 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.
User avatar
pickle
Briney Mod
Posts: 6445
Joined: Mon Jan 19, 2004 6:11 pm
Location: 53.01N x 112.48W
Contact:

Re: Matching closest long/lat

Post 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.
Real programmers don't comment their code. If it was hard to write, it should be hard to understand.
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Re: Matching closest long/lat

Post 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.
User avatar
pickle
Briney Mod
Posts: 6445
Joined: Mon Jan 19, 2004 6:11 pm
Location: 53.01N x 112.48W
Contact:

Re: Matching closest long/lat

Post 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
Real programmers don't comment their code. If it was hard to write, it should be hard to understand.
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Re: Matching closest long/lat

Post by John Cartwright »

Thanks for the links. I will let you know how it goes.
Post Reply