-1

I'm working on an implementation for finding the nearest person based on geographic coordinates. For example, person A has coordinates（Longitude and latitude ） m, and I want to find the person within the circle of center m with radius x.

I plan to store the geographic coordinates in a MySQL database, what's the efficient way to search the nearest coordinates?

My specific question is:

  1. what fields should be stored in database for efficient search? I plan to store persons' coordinates only.
  2. what's the algorithm for finding the nearest person? I plan to calculate the distance between person A's coordinate and the coordinates stores in the database.

However, I think it is less efficient to calculate if the number of coordinates is huge in the database.

What's the better way to achieve this application?

Barranka
  • 20,547
  • 13
  • 65
  • 83
user3784595
  • 13
  • 4
  • 1
    How about just extracting everyone that has an X or Y coordinate that could *potentially* be within the radius, and then doing the radius calculation on that? – Lasse V. Karlsen Jun 27 '14 at 21:00
  • If you care about performance, I would definitely consider a column-oriented DB for this kind of problem. – pamphlet Jun 27 '14 at 21:00
  • A "column oriented DB"? If his database wasn't "column oriented" it would probably be one of the NoSQL databases, which would still, to a certain degree, care about "columns" (or document properties). – Lasse V. Karlsen Jun 27 '14 at 21:03
  • Column-oriented vs row-oriented: http://en.wikipedia.org/wiki/Column-oriented_DBMS. Both have "columns". One stares the data by column, the other by row. – pamphlet Jun 27 '14 at 21:04
  • possible duplicate of [Finding the closest point to a given point](http://stackoverflow.com/questions/913576/finding-the-closest-point-to-a-given-point) – SergeyB Jun 27 '14 at 21:11

2 Answers2

0

A simple Pithagoras theorem application:

-- The coordinates of the person at the center of the "circle"
set @x0 = (select x from persons where id=1),
    @y0 = (select y from persons where id=1);
-- Calculate the distance for each point in the persons table, excluding the "center"
select *, sqrt(pow(x - @x0, 2) + pow(y - @y0, 2)) as distance
from persons
where id != 1
order by sqrt(pow(x - @x0, 2) + pow(y - @y0, 2))
Barranka
  • 20,547
  • 13
  • 65
  • 83
  • 1
    SqRt is not needed (speed increase). Instead if someone says within 4 miles, you Square that value (16), now SqRt is not needed on every row. – Erik Philips Jun 30 '14 at 03:36
  • @ErikPhilips You are right... it can be removed from the `order by` clause – Barranka Jun 30 '14 at 03:38
0

I realize this talks about SQL Server specifically, and not MySql. However, that does not mean you cannot implement a similar solution. (and it seems MySql has Spatial Indexes).

This is implemented in multiple database technologies using grids. There a great video that goes in depth about how grid coordinates works on sql bits called Creating High Performance Spatial Database.

Here are a few images of the grid technique from MSDN Spatial Indexing Overview.

Break down the earth into multiple level grids.

enter image description here

Locate which grids contain some or all of the object (square, circle, whatever)..

enter image description here

This technique allows inclusion and exclusion very quickly without the need to calculate distance on every object (time consuming crazy like).

Erik Philips
  • 53,428
  • 11
  • 128
  • 150