[postgis-users] Find n Nearest Neighbors for given Point using PostGIS?

[Ben Madin]

Have you tried EXPLAIN to see where the slow part is?

But at a guess - consider that st_dwithin uses the geometry unit for it's calculations - so you are searching for everything within 300 degrees (more than halfway around the planet). You may want to try searching a smaller set of data before you sort it to find the closest five.

cheers

Ben

On 25/02/2011, at 12:04 PM, Scholle wrote:

> 
> I am trying to solve the problem of finding the n nearest neighbors using
> PostGIS:
> 
> Starting Point:
> 
> - Table geoname with geonames (from geonames.org) containing
> latitude/longitude (WSG-84)
> - Added a GeometryColumn geom with srid=4326 and datatype=POINT
> - Filled geom with values: UPDATE geoname SET geom =
> ST_SetSRID(ST_Point(longitude,latitude) 4326);
> - Created GIST index for geom (CREATE INDEX geom_index ON geoname USING
> GIST (geom);) / Clustered geom_index: CLUSTER geom_index ON geoname;)
> - Created PRIMARY KEY UNIQUE BTREE index for geonameid
> 
> Problem:
> Find n (e.g. 5) nearest neighbors for a given Point in table geoname
> represented by id (geoname.geonameid.
> 
> Possible solution:
> 
> Inspired by
> http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_nearest_neighbor,
> I tried the following query:
> 
> "SELECT start.asciiname, ende.asciiname, distance_sphere(start.geom,
> ende.geom) as distance " +
> "FROM geoname As start, geoname As ende WHERE start.geonameid = 2950159 AND
> start.geonameid <> ende.geonameid " +
> "AND ST_DWithin(start.geom, ende.geom, 300) order by distance limit 5"
> 
> Processing time: about 60s
> 
> Also tried an approach based on EXPAND:
> 
> "SELECT start.asciiname, ende.asciiname, distance_sphere(start.geom,
> ende.geom) as distance " +
> "FROM geoname As start, geoname As ende WHERE start.geonameid = 2950159 AND
> start.geonameid <> ende.geonameid AND expand(start.geom, 300) && ende.geom "
> +
> "order by distance limit 5"
> 
> Processing time: about 120s
> 
> The intended application is some kind of autocomplete. So, any approach
> taking longer than <1s is not applicable. Is it generally possible to
> achieve such a response time with PostGIS? 
> -- 
> View this message in context: http://old.nabble.com/Find-n-Nearest-Neighbors-for-given-Point-using-PostGIS--tp31010122p31010122.html
> Sent from the PostGIS - User mailing list archive at Nabble.com.
> 
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users