PostGIS中的K最近邻查询

Question

我在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;

现在，我已经在两个表的the_geom和gid列上创建了索引，但这个查询却比涉及两个表之间空间连接的其他空间查询需要更多时间。

有没有更好的方法来查找K近邻？我正在使用PostGIS。

另一个查询尽管在几何列上创建了索引，但却需要异常长的时间：

select g1.gid , g2.gid from polygons as g1 , polygons as g2
where st_area(g1.the_geom) > st_area(g2.the_geom) ;

我认为，这些查询不会受到gist索引的好处，但是为什么呢？

而这个查询语句：

select a.polyid , sum(length(b.the_geom)) from polygon as a , roads as b  
where st_intersects(a.the_geom , b.the_geom);

尽管涉及比多边形或点表更大的"roads"表，还涉及更复杂的空间运算符，但会在一段时间后返回结果。

- Abhishek Sagar

---

我猜你的问题是如何加快查询速度？能否向我们展示 EXPLAIN ANALYZE SELECT .... 的结果？这样或许我们就能知道出了什么问题。 - Thilo

不，我的问题是为什么这个查询所花费的时间甚至比上面第三个查询所花费的时间多了5倍以上！！ - Abhishek Sagar

好的，经过漫长的等待，对于第二个查询，我收到了以下错误消息：“查询结果内存不足”，并且查询执行被终止。有人能解释一下吗？ - Abhishek Sagar

Answer 1

自从2011年9月底以来，PostGIS通过特殊的操作符在ORDER BY子句中支持索引最近邻查询：

SELECT name, gid
FROM geonames
ORDER BY geom <-> st_setsrid(st_makepoint(-90,40),4326)
LIMIT 10;

这将以可扩展的方式返回距离 -90,40 最近的10个对象的geom。更多详细信息（选项和注意事项）在此公告post和<->和<#>运算符的使用在正式的PostGIS 2.0参考文档中也有记录。（两者之间的主要区别在于<->比较形状的质心，而<#>比较它们的边界-对于点来说没有区别，对于其他形状，请选择适合您的查询的运算符。）

- natevw

---

这两个运算符的一个重要限制，如链接的postgis参考页面所述，是只有当其中一个几何体是常量，例如在示例中的st_makepoint时，空间索引才会起作用。这意味着您无法使用这些运算符来高效地使用索引回答原始问题，该问题涉及查找所有几何体A与另一组几何体B接近的情况。 - John Powell

啊，说得好。感谢你提出这个问题。那么@Stefan的回答就是“正确”的了，只需要更多的细节和更新的链接吗？ - natevw

Answer 2

关于你的问题，我有几点想法：

st_distance和st_area都不能使用索引。这是因为这两个函数不能简化成像“a是否在b中？”或“a和b是否重叠？”这样的问题。更具体地说：GIST索引只能操作两个对象的边界框。

如果需要了解更多信息，可以查看postgis手册，其中提供了使用st_distance进行查询并使其性能更好的示例。

然而，这并不能解决你的k最近邻问题。目前，我没有很好的想法来提高查询性能。我唯一看到的机会就是假设k个最近邻总是在x米以下的距离内。然后，你可以使用与postgis手册中类似的方法。

你的第二个查询可以稍微加速一些。当前，你针对表1中的每个对象计算面积的次数与表格行数相同。首先加入数据，然后基于该函数进行选择。你可以通过预先计算面积来显着减少计算面积的数量：

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;

使用边界框可以大幅优化您的第三个查询：当两个对象的边界框不重叠时，则不存在对象间的关联。这允许使用特定索引，从而获得巨大的性能提升。

- Thilo

Answer 3

你可以通过使用KNN索引和侧向连接来完成这个操作。

SELECT v.gid, v2.gid,st_distance(v.the_geom, v2.the_geom)
  FROM geonames v, 
       lateral(select * 
                 from geonames v2
                where v2.id<>v.id
                ORDER BY v.the_geom <-> v2.the_geom LIMIT 10) v2
where v.gid in (...) - or other filtering condition

- Grzegorz Grabek

Answer 4

你可能需要的是KNN索引，它很快就会在PostGIS 2.x和PostgreSQL 9.1中提供：请参见http://blog.opengeo.org/tag/knn/。

- Stefan

Answer 5

假设您有p个点和g个多边形，您的原始查询如下：

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;

返回p x g集合中k个最近的邻居。查询可能使用索引，但仍然必须对整个p x g集合进行排序，以找到具有最小距离的k行。相反，您需要的是以下内容：

SELECT g1.gid, 
      (SELECT g2.gid FROM polygons g2   
       --prevents you from finding every nearest neighbour twice
       WHERE g1.gid < g2.gid 
       --ORDER BY gid is erroneous if you want to limit by the distance
       ORDER BY ST_Distance(g1.the_geom,g2.the_geom)
       LIMIT k)
FROM points as g1;

- raphael