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) ;

我相信,这些查询并没有受到主要指标的影响,但为什么呢？

鉴于此查询:

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

尽管涉及比"多边形"或"点"表大得多的"道路"表并且还涉及更复杂的空间算子,但是在一段时间之后返回结果.

Answer 1

自2011年9月下旬以来,PostGIS通过ORDER BY子句中可用的特殊运算符支持索引的最近邻居查询:

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

...将以可伸缩的方式返回geom最近的10个对象-90,40.一些更多的细节(选项和注意事项),是在公告后和使用的< - >和的<#>运营商现在也官方PostGIS的2.0参考文件.(两者之间的主要区别在于<->比较形状质心并<#>比较它们的边界 - 点没有区别,其他形状选择适合您的查询.)

Answer 2

关于你的问题的一些想法:

st_distance和st_area无法使用索引.这是因为这两个功能都不能简化为"是否在b内？"之类的问题.或"做a和b重叠？".更具体:GIST-indices只能在两个对象的边界框上运行.

有关这方面的更多信息,您可以查看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;

使用边界框可以显着优化您的第三个查询:当两个对象的边界框不重叠时,对象无法做到.这允许使用给定的索引并因此获得巨大的性能增益.

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