K-gần Neighbor Query trong PostGIS

Question

Tôi đang sử dụng hàng xóm gần sau Query trong 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; 

Bây giờ, mà tôi đã tạo ra chỉ số về the_geom cũng như cột gid trên cả hai bảng, truy vấn này là mất nhiều thời gian hơn so với các truy vấn không gian khác liên quan đến tham gia không gian b/w hai bảng.

Có cách nào tốt hơn để tìm hàng xóm gần nhất của K không? Tôi đang sử dụng PostGIS.

Và, một truy vấn được tham gia một thời gian dài bất thường mặc dù tạo chỉ số trên cột hình học là:

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

Tôi tin rằng, các truy vấn arent hưởng lợi bởi chỉ số ý chính, nhưng tại sao?

Trong khi truy vấn này:

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

trả về kết quả sau một thời gian mặc dù liên quan đến "con đường" bảng mà là lớn hơn nhiều so với đa giác hoặc bảng điểm và cũng liên quan đến khai thác không gian phức tạp hơn.

Answer 1

Chỉ cần một vài suy nghĩ về sự cố của bạn:

st_distance cũng như st_area không thể sử dụng chỉ mục. Điều này là do cả hai chức năng không thể được giảm xuống thành các câu hỏi như "Có phải trong b?" hoặc "Do a và b overlap?". Bê tông thậm chí nhiều hơn: Chỉ số GIST chỉ có thể hoạt động trên các hộp giới hạn của hai đối tượng.

Để biết thêm thông tin về điều này, bạn chỉ có thể xem trong số postgis manual, trong đó nêu rõ ví dụ về tính không xác định và cách truy vấn có thể được cải thiện để hoạt động tốt hơn.

Tuy nhiên, điều này không giải quyết được vấn đề k-láng giềng gần nhất của bạn. Đối với điều đó, ngay bây giờ tôi không có một ý tưởng tốt như thế nào để cải thiện hiệu suất của truy vấn. Cơ hội duy nhất tôi thấy là giả định rằng k hàng xóm gần nhất luôn ở khoảng cách dưới x mét. Sau đó, bạn có thể sử dụng một cách tiếp cận tương tự như được thực hiện trong hướng dẫn sử dụng postgis.

Truy vấn thứ hai của bạn có thể được tăng tốc một chút. Hiện tại, bạn tính toán diện tích cho từng đối tượng trong bảng 1 thường xuyên như bảng có các hàng - chiến lược đầu tiên là tham gia dữ liệu và sau đó chọn dựa trên hàm đó. Bạn có thể làm giảm số lượng các tính toán diện tích được đáng kể precomputing khu vực:

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; 

truy vấn thứ ba của bạn có thể được tối ưu hóa đáng kể sử dụng hộp bounding: Khi các hộp giới hạn của hai đối tượng không chồng chéo lên nhau, không có cách nào các đối tượng làm . Điều này cho phép sử dụng một chỉ mục nhất định và do đó đạt được hiệu suất rất lớn.

Answer 2

Những gì bạn có thể cần phải là chỉ số KNN đó là hy vọng sớm trong PostGIS 2.x và PostgreSQL 9.1: Xem http://blog.opengeo.org/tag/knn/

Answer 3

Kể từ late September 2011, PostGIS đã hỗ trợ các truy vấn hàng xóm gần nhất lập chỉ mục thông qua một nhà điều hành đặc biệt (s) có thể sử dụng trong mệnh đề ORDER BY:

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

... sẽ trở lại với 10 đối tượng có geom là khu vực gần -90,40 một cách mở rộng.Một vài chi tiết khác (tùy chọn và cẩn thận) có trong thông báo đó post và use of the <-> và the <#> operators cũng được ghi lại trong tài liệu tham khảo chính thức của PostGIS 2.0. (Sự khác biệt chính giữa hai là <-> so sánh các hình dạng centroids và <#> so sánh ranh giới của họ - không có sự khác biệt cho điểm, hình dạng khác chọn những gì là thích hợp cho các truy vấn của bạn.)

Answer 4

Giả sử bạn có p điểm và g đa giác, của bạn truy vấn ban đầu:

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; 

Trả lại k hàng xóm gần nhất trong tập hợp pxg. Truy vấn có thể đang sử dụng các chỉ mục, nhưng nó vẫn phải đặt toàn bộ tập hợp p x g để tìm k hàng có khoảng cách nhỏ nhất. Thay vào đó, những gì bạn muốn là:

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;