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
