Re: [postgis-users] Find n Nearest Neighbors for given Point using PostGIS?
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 > Subject: Re: [postgis-users] Find n Nearest Neighbors for given Point > using PostGIS? > To: postgis-users@postgis.refractions.net > Message-ID: <31010203.p...@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? > >> -- > ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
Re: [postgis-users] Find n Nearest Neighbors for given Point using PostGIS?
Scholle, The only way you can do nearest neighbor searches the are fast is to write a stored procedure that expands the search if you fail to get the number of results you want. So in pseudo code something like: radius := 0.01; -- assuming degrees loop select into cnt count(*) from mytable where expand(mypnt, radius) && the_geom limit 5; if found and cnt = 5 or radius > maxradius then for rr in select * from mytable where expand(mypnt, radius) && the_geom limit 5 loop return rr; end loop; return; else radius := radius * 2; end if; end loop; So make a set returning function with the body something like this and you should get good performance. Because postgresql, does a really good job of caching pages and query results you will not pay much of a penalty for the repeated queries. -Steve On 2/24/2011 11: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" The problem here is that you are expanding your search by 300 degrees if your data is in WGS84. 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? ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
Re: [postgis-users] Find n Nearest Neighbors for given Point using PostGIS?
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? >> -- >> 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@postgis.refractions.net >> http://postgis.refractions.net/mailman/listinfo/postgis-users > > ___ > postgis-users mailing list > postgis-users@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. ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
Re: [postgis-users] Find n Nearest Neighbors for given Point using PostGIS?
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@postgis.refractions.net > http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
[postgis-users] Find n Nearest Neighbors for given Point using PostGIS?
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@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
