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

Scholle mstumpp at gmail.com
Thu Feb 24 20:38:36 PST 2011

```Great, didn't consider the geometry/degree difference.... I drastically
decreased the value for the third parameter of ST_DWithin function and its
sufficiently fast now...

>
> 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"
>>
>>
>> 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"
>>
>>
>> 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
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>
>

--
View this message in context: http://old.nabble.com/Find-n-Nearest-Neighbors-for-given-Point-using-PostGIS--tp31010122p31010203.html
Sent from the PostGIS - User mailing list archive at Nabble.com.

```