K-Nearest Neighbor Query in PostGIS

Question

I am using the following Nearest Neighbor Query in PostGIS : ``` SELECT g1.gid g2.gid FROM points as g1, polygons g2 WHERE g1.gid <> g2.gid ORDER BY g1.gid, ST_Distance(g1.the_geom,g2.the_geom) LIMIT k; ``` Now, that I have created indexes on the_geom as well as gid column on both the tables, this query is taking much more time than other spatial queries involving spatial joins b/w two tables. Is there any better way to find K-nearest neighbors? I am using PostGIS. And, another query which is taking a unusually long time despite creating indexes on geometry column is: ``` select g1.gid , g2.gid from polygons as g1 , polygons as g2 where st_area(g1.the_geom) > st_area(g2.the_geom) ; ``` I believe, these queries arent benefited by gist indexes, but why? Whereas this query: ``` select a.polyid , sum(length(b.the_geom)) from polygon as a , roads as b where st_intersects(a.the_geom , b.the_geom); ``` returns result after some time despite involving "roads" table which is much bigger than p…

Accepted Answer

Just a few thoughts on your problem:

st_distance as well as st_area are not able to use indices. This is because both functions can not be reduced to questions like "Is a within b?" or "Do a and b overlap?". Even more concrete: GIST-indices can only operate on the bounding boxes of two objects.

For more information on this you just could look in the postgis manual, which states an example with st_distance and how the query could be improved to perform better.

However, this does not solve your k-nearest-neighbour-problem. For that, right now I do not have a good idea how to improve the performance of the query. The only chance I see would be assuming that the k nearest neighbors are always in a distance of below x meters. Then you could use a similar approach as done in the postgis manual.

Your second query could be speeded up a bit. Currently, you compute the area for each object in table 1 as often as table has rows - the strategy is first to join the data and then select based on that function. You could reduce the count of area computations significantly be precomputing the area:

```
WITH polygonareas AS (
    SELECT gid, the_geom, st_area(the_geom) AS area
    FROM polygons
)
SELECT g1.gid, g2.gid
FROM polygonareas as g1 , polygonareas as g2 
WHERE g1.area > g2.area;
```

Your third query can be significantly optimized using bounding boxes: When the bounding boxes of two objects do not overlap, there is no way the objects do. This allows the usage of a given index and thus a huge performance gain.

K-Nearest Neighbor Query in PostGIS

Solution

Problem