2

What would be the best way to store data in a database for geographical calculations? Say I have an ItemsForSale table paired to a Users table which holds their geo location. I know I can use latitude and longitude to look up items that are within a certain mile radius by using Lambert's formula for long lines or the Haversine formula but I am not sure if there is a better approach for this.

Adrian
  • 175
  • 1
  • 6
  • Have you checked if Google Maps has an API for this situation ? – Radu Murzea Mar 22 '14 at 18:05
  • 1
    Yes but there are limits to the service. In my situation I can see multiple users wanting to find items within a 50 mile radius and having thousands of items in the `ItemsForSale` table to sift through and check off if the distance is within the limit. That would quickly outrun the service. https://developers.google.com/maps/documentation/distancematrix/ – Adrian Mar 22 '14 at 18:15
  • Check the documentation for the database you're using. Many have native support or extensions for storing geographic types and can do exactly the kind of query you're after with almost no effort. – Blrfl Mar 22 '14 at 18:46
  • Check out MaxMind's *free* [GeoLite](http://dev.maxmind.com/geoip/legacy/geolite/) databases and code. They may not completely cover your needs, but we found them very useful in a couple of projects. – Peter Rowell Mar 22 '14 at 22:29
  • Related: StackOverflow: [What is the best way to store geographic coordinate data in a database](http://stackoverflow.com/q/6665894/289086), [Find all coordinates within a circle in geographic data in python](http://stackoverflow.com/q/6371187/289086). Note the [geospatial](http://stackoverflow.com/questions/tagged/geospatial) tag. You may also find [GIS.StackExchange](http://gis.stackexchange.com) to be useful. –  Oct 29 '14 at 20:24

1 Answers1

1

I'm not sure standard databases like MySql provide spacial indexing. You need to put them in a persistent spacial index. Like M-trees. Spacial indexes are efficient data structures that can perform range queries over distance metrics.

You might be able to find an implementation of M-tree or other spacial indexing data structures like K-D trees.

EDIT: After Martijn Pieters mentioned MySql having spatial indexes, I looked it up. Turns out it does have a R-tree but the support doesn't seem great. I only use innodb because mostly I end up requiring row level locks.

MySQL 5.6 implements an additional set of functions that can help create geo-enabled applications with MySQL. Storing polygons boundaries (ZIP code boundaries for example) is efficient and the new spatial functions (st_within, st_contains, etc) will produce correct results and will use spatial (rtree) indexes (for MyISAM tables only). The OpenGIS standard is very common and it is easy to obtain the data in this format or use the standard application which can “talk” this language. Unfortunately, st_distance function is not very usable for calculating distance between 2 points on Earth and it does not use an index. In this case it is still more feasible to calculate distances manually using the harvesine formula. Hopefully this will be fixed in the next mysql release.

Community
  • 1
Neo M Hacker
  • 156
  • 3