[prev in list] [next in list] [prev in thread] [next in thread]
List: postgis-users
Subject: Re: [postgis-users] Find n Nearest Neighbors for given Point using
From: Ragi Burhum <rburhum () gmail ! com>
Date: 2011-02-26 19:32:52
Message-ID: AANLkTimrCnvKRSL05dpUqMVn29MeYaMZKY4VpaE+-xay () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
Another solution is to use a knngist index. It will most likely be
incorporated in a future version of PostGIS. Since it looks like it was
already commited in PostgreSQL trunk, and if you have one of those
brave-trunk-running souls, you should be able to test it with a beta version
of PostgreSQL. You will get a considerable speed gain from using this
approach.
- Ragi
Date: Thu, 24 Feb 2011 20:38:36 -0800 (PST)
> From: Scholle <mstumpp@gmail.com>
> Subject: Re: [postgis-users] Find n Nearest Neighbors for given Point
> using PostGIS?
> To: postgis-users@postgis.refractions.net
> Message-ID: <31010203.post@talk.nabble.com>
> Content-Type: text/plain; charset=us-ascii
>
>
> 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...
>
>
>
>
> Ben Madin-3 wrote:
> >
> > 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?
> >> --
>
[Attachment #5 (text/html)]
<div>Another solution is to use a knngist index. It will most likely be incorporated \
in a future version of PostGIS. Since it looks like it was already commited in \
PostgreSQL trunk, and if you have one of those brave-trunk-running souls, you should \
be able to test it with a beta version of PostgreSQL. You will get a considerable \
speed gain from using this approach.</div> <div><br></div><div>- Ragi</div><br>Date: \
Thu, 24 Feb 2011 20:38:36 -0800 (PST)<br><div class="gmail_quote"><blockquote \
class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex;">
From: Scholle <<a href="mailto:mstumpp@gmail.com">mstumpp@gmail.com</a>><br>
Subject: Re: [postgis-users] Find n Nearest Neighbors for given Point<br>
using PostGIS?<br>
To: <a href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</a><br>
Message-ID: <<a href="mailto:31010203.post@talk.nabble.com">31010203.post@talk.nabble.com</a>><br>
Content-Type: text/plain; charset=us-ascii<br>
<br>
<br>
Great, didn't consider the geometry/degree difference.... I drastically<br>
decreased the value for the third parameter of ST_DWithin function and its<br>
sufficiently fast now...<br>
<br>
<br>
<br>
<br>
Ben Madin-3 wrote:<br>
><br>
> Have you tried EXPLAIN to see where the slow part is?<br>
><br>
> But at a guess - consider that st_dwithin uses the geometry unit for \
it's<br> > calculations - so you are searching for everything within 300 \
degrees<br> > (more than halfway around the planet). You may want to try searching \
a<br> > smaller set of data before you sort it to find the closest five.<br>
><br>
> cheers<br>
><br>
> Ben<br>
><br>
> On 25/02/2011, at 12:04 PM, Scholle wrote:<br>
><br>
>><br>
>> I am trying to solve the problem of finding the n nearest neighbors \
using<br> >> PostGIS:<br>
>><br>
>> Starting Point:<br>
>><br>
>> - Table geoname with geonames (from <a href="http://geonames.org" \
target="_blank">geonames.org</a>) containing<br> >> latitude/longitude \
(WSG-84)<br> >> - Added a GeometryColumn geom with srid=4326 and \
datatype=POINT<br> >> - Filled geom with values: UPDATE geoname SET geom =<br>
>> ST_SetSRID(ST_Point(longitude,latitude) 4326);<br>
>> - Created GIST index for geom (CREATE INDEX geom_index ON geoname USING<br>
>> GIST (geom);) / Clustered geom_index: CLUSTER geom_index ON geoname;)<br>
>> - Created PRIMARY KEY UNIQUE BTREE index for geonameid<br>
>><br>
>> Problem:<br>
>> Find n (e.g. 5) nearest neighbors for a given Point in table geoname<br>
>> represented by id (geoname.geonameid.<br>
>><br>
>> Possible solution:<br>
>><br>
>> Inspired by<br>
>> <a href="http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_nearest_neighbor" \
target="_blank">http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_nearest_neighbor</a>,<br>
>> I tried the following query:<br>
>><br>
>> "SELECT start.asciiname, ende.asciiname, \
distance_sphere(start.geom,<br> >> ende.geom) as distance " +<br>
>> "FROM geoname As start, geoname As ende WHERE start.geonameid = \
2950159<br> >> AND<br>
>> start.geonameid <> ende.geonameid " +<br>
>> "AND ST_DWithin(start.geom, ende.geom, 300) order by distance limit \
5"<br> >><br>
>> Processing time: about 60s<br>
>><br>
>> Also tried an approach based on EXPAND:<br>
>><br>
>> "SELECT start.asciiname, ende.asciiname, \
distance_sphere(start.geom,<br> >> ende.geom) as distance " +<br>
>> "FROM geoname As start, geoname As ende WHERE start.geonameid = \
2950159<br> >> AND<br>
>> start.geonameid <> ende.geonameid AND expand(start.geom, 300) \
&&<br> >> ende.geom "<br>
>> +<br>
>> "order by distance limit 5"<br>
>><br>
>> Processing time: about 120s<br>
>><br>
>> The intended application is some kind of autocomplete. So, any approach<br>
>> taking longer than <1s is not applicable. Is it generally possible to<br>
>> achieve such a response time with PostGIS?<br>
>> --<br></blockquote></div>
_______________________________________________
postgis-users mailing list
postgis-users@postgis.refractions.net
http://postgis.refractions.net/mailman/listinfo/postgis-users
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic