Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

Say I want to find 20 closest business near me.

My table structure is like this:

    BusinessID  varchar(250)    utf8_unicode_ci         No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
    Prominent   double          No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
    LatLong     point           No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
    FullTextSearch  varchar(600)    utf8_bin        No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
With selected: Check All / Uncheck All With selected:
Print viewPrint view Propose table structurePropose table structureDocumentation
Add new fieldAdd field(s) At End of Table At Beginning of Table After
Indexes: Documentation
Action  Keyname Type    Unique  Packed  Field   Cardinality Collation   Null    Comment
Edit    Drop    PRIMARY BTREE   Yes No  BusinessID  1611454 A       
Edit    Drop    Prominent   BTREE   No  No  Prominent   0   A       
Edit    Drop    LatLong BTREE   No  No  LatLong (25)    0   A       
Edit    Drop    sx_mytable_coords   SPATIAL No  No  LatLong (32)    0   A       
Edit    Drop    FullTextSearch  FULLTEXT    No  No  FullTextSearch  0           

There are 1.6 million bizs. Of course it's stupid to compute distance for all of them and then sort it.

That's where geo spatial index kicks in right?

So what SQL comman I need to cast?

Note:

  1. I am using mysql myisam spatial index. However I did not specify this before. So I will accept those who answer it to show my appreciation and ask another question.
  2. I do not want to compute distance for the whole table
  3. I do not want to compute distance for any region which are still inefficient
  4. I do want to compute distance for reasonable number of points because I want to sort the points by distance and be able to display point 1-20, 21-40, 41-60, etc.
share|improve this question
    
Why the downvotes? –  Jim Thio Jun 21 '12 at 7:49
add comment

3 Answers

up vote 5 down vote accepted

Spatial queries are definitely the thing to use.

With PostGIS I would first try something simplistic like this and tweak the range as needed:

SELECT * 
FROM table AS a
WHERE ST_DWithin (mylocation, a.LatLong, 10000) -- 10km
ORDER BY ST_Distance (mylocation, a.LatLong)
LIMIT 20

This would compare points (actually their bounding boxes) using the spatial index, so it should be fast. Another approach that comes to mind is buffering your location and then intersecting that buffer with the original data, which may be even more efficient.

share|improve this answer
    
will this fine 20 closest points? I don't care about filter. I just want 20 closest points. Result should be sorted based on distance and the 20 closest points will show up first, the the next 20, etc. –  Jim Thio Jun 20 '12 at 21:14
2  
You skipped the ORDER BY step. Cull to a reasonable size with the WHERE, then do and sort by the proper distance measurement. –  zebediah49 Jun 20 '12 at 21:18
    
thanks, I ammended the answer. Jim, if you need all within the arbitrary range, just remove the LIMIT, which is now set to return only the 20 closest points. –  lynxlynxlynx Jun 20 '12 at 21:34
    
you sure they don't compute distance for all points within 10000? There are 67k points and that's still too many. –  Jim Thio Jun 21 '12 at 2:40
    
Actually this is what I need because there is nothing better. Would this work in mysql? –  Jim Thio Jun 21 '12 at 6:56
show 2 more comments

With PostGIS 2.0 on PostgreSQL 9.1, you can use the KNN indexed nearest neighbour operator, e.g.:

SELECT *, geom <-> ST_MakePoint(-90, 40) AS distance
FROM table
ORDER BY geom <-> ST_MakePoint(-90, 40)
LIMIT 20 OFFSET 0;

The above should query within a few milliseconds.

For the next multiples of 20, modify to OFFSET 20, OFFSET 40, etc ...

share|improve this answer
add comment

If all you are looking for are proximity point searches (nearest neighbour queries), then you don't want to use the old ST_DWithin or ST_Distance + ORDER BYs for that.

Not anymore.

Now that PostGIS 2.0 shipped, you should be using the knngist index support (a native PostgreSQL feature). It will be orders of magnitude faster.

An excerpt from this blog entry that describes how to use knn gist without PostGIS:

$ create table test ( position point );

CREATE TABLE
Table created. Now let’s insert some random points:
$ insert into test (position) select point( random() * 1000, random() * 1000) from generate_series(1,1000000);

INSERT 0 1000000
1 million points should be enough for my example. All of them have both X and Y in range <0, 1000). Now we just need the index:
$ create index q on test using gist ( position );

CREATE INDEX
And we can find some rows close to center of the points cloud:
$ select *, position <-> point(500,500) from test order by position <-> point(500,500) limit 10;

              position               |     ?column?

-------------------------------------+-------------------

 (499.965638387948,499.452529009432) | 0.548548271254899

 (500.473062973469,500.450353138149) |  0.65315122744144

 (500.277776736766,500.743471086025) | 0.793668174518778

 (499.986605718732,500.844359863549) | 0.844466095200968

 (500.858531333506,500.130807515234) | 0.868439207229501

 (500.96702715382,499.853323679417)  | 0.978087654172406

 (500.975443981588,500.170825514942) | 0.990289007195055

 (499.201623722911,499.368405900896) |  1.01799596553335

 (498.899147845805,500.683960970491) |  1.29602394829404

 (498.38217580691,499.178630765527)  |  1.81438764851559

(10 rows)
And how about speed?
$ explain analyze select *, position <-> point(500,500) from test order by position <-> point(500,500) limit 10;

                                                        QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------

 Limit  (cost=0.00..0.77 rows=10 width=16) (actual time=0.164..0.475 rows=10 loops=1)

   ->  Index Scan using q on test  (cost=0.00..76512.60 rows=1000000 width=16) (actual time=0.163..0.473 rows=10 loops=1)

         Order By: ("position" <-> '(500,500)'::point)

 Total runtime: 0.505 ms

(4 rows)

Interesting enough, the index traversal will return the features in order of proximity, so no need to do a sort (i.e order by) for the results!

However, if you want to use it alongside PostGIS, now it is really easy. Just follow these instructions.

The relevant part is this:

SELECT name, gid
FROM geonames
ORDER BY geom <-> st_setsrid(st_makepoint(-90,40),4326)
LIMIT 10;

But don't take my word of it. Time it yourself :)

share|improve this answer
    
This will be a good answer. However, I am using mysql myisam. I forget to add that. –  Jim Thio Jun 21 '12 at 2:41
    
So +1 but I can't select this as my answer. Should I create another question? –  Jim Thio Jun 21 '12 at 3:52
    
@JimThio MySQL does not have a nearest neighbor index so you will have to rely on the PostGIS-like approach before there was a nearest neighbor query (ST_Dwithin with ORDER BY ST_Distance). Welcome back to the middle ages :) –  Ragi Yaser Burhum Jun 21 '12 at 6:29
    
So I got to go to mongodb? Let me guess. What's the point of having a spatial index on mysql if you cannot even do the simplest thing like finding 20 closest points? –  Jim Thio Jun 21 '12 at 6:31
1  
You can find the closest point using a window. The same is true for any other spatial database as described by @lynxlynxlynx. You can keep increasing the window by multiplying it by two. Yes, the same is true for Mongo or any other database. The point is that you cut down in most of the other features. Besides, everyone knows that until just recently, MySQL was never a serious contender for anything spatial. –  Ragi Yaser Burhum Jun 21 '12 at 6:37
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.