1

I am designing an android app that will display points of interest (POIs) near you. The POIs will be stored in a database, which I would like to be able to efficiently search for the POIs near me and have the search return a sorted list of perhaps the 100 closest locations.

I am wondering how I should design my database so that it can be efficiently searched. Are there any specific forms of SQL that I should use, or any special algorithms to speed up the search? While it won't be a problem if I only have 100 locations in my database, I can imagine it might get difficult if I have 10,000 or more.

Neil McGuigan
  • 46,580
  • 12
  • 123
  • 152
Jonathon Vandezande
  • 2,446
  • 3
  • 22
  • 31
  • Something like [this](http://stackoverflow.com/questions/3695224/android-sqlite-getting-nearest-locations-with-latitude-and-longitude)? – PinnyM Sep 30 '12 at 02:10

2 Answers2

1

Use a database with good multi-dimensional indexing. This allows the database to do efficient bounding box queries. PostgreSQL is good choice, as it has GIST indices for bounding box queries. MySQL and MS SQL have acceptable functionality.

The other issue you face is the choice of coordinate systems. GPS Lat, Long coordinates are angles. So there is choice of How to do the distance math.

1) Converting all Lat, Long to Cartesian X,Y coordinates - This works for small (US state) sized areas. This requires map projection functions to convert between lat,Long and Cartesian coords.

2) Use a haversine formula http://www.movable-type.co.uk/scripts/latlong.html. But careful! as the index keys are in Lat,Longs. There can be side effects to this choice.

PostGIS is a PostgreSQL GIS application. It's heavy weight for nearest point queries but works.

Tim Child
  • 2,994
  • 1
  • 26
  • 25
0

use PostGIS

http://en.wikipedia.org/wiki/PostGIS

Neil McGuigan
  • 46,580
  • 12
  • 123
  • 152