K-Najbliższy sąsiad Zapytanie w PostGIS

Question

Używam następujący najbliższego sąsiada kwerend w 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; 

teraz, że stworzyliśmy indeksy na the_geom jak gid kolumnowej na obu tablicach, to zapytanie jest zajmuje dużo więcej czasu niż inne zapytania przestrzenne związane z połączeniami przestrzennymi b/w dwie tabele.

Czy istnieje lepszy sposób na znalezienie najbliższych sąsiadów K? Używam PostGIS.

I kolejna kwerenda, która bierze niezwykle długo, mimo tworzenia indeksów na kolumny geometrii:

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

wierzę, te pytania arent korzystał przez indeksy GIST, ale dlaczego?

niniejsza zapytania:

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

powraca spowodować po pewnym czasie mimo udziałem „dróg” stół, który jest znacznie większy niż wielokątów lub punkty tabeli i obejmować również bardziej złożone operatory przestrzenne.

Answer 1

Zaledwie kilka myśli na temat swojego problemu:

st_distance jak st_area nie są w stanie korzystać z indeksów. Jest tak dlatego, że obie funkcje nie mogą być zredukowane do pytań typu "Czy jest w b?" lub "Czy nakładają się a i b?". Jeszcze bardziej konkretny: wskaźniki GIST mogą działać tylko na obwiedniach dwóch obiektów.

Aby uzyskać więcej informacji na ten temat, wystarczy spojrzeć na numer postgis manual, który podaje przykład ze st_distance i jak można ulepszyć zapytanie, aby działał lepiej.

Nie rozwiąże to jednak problemu k-najbliższego-sąsiada. W tym momencie nie mam dobrego pomysłu, jak poprawić wydajność zapytania. Jedyną szansą, jaką widzę, byłoby założenie, że najbliżsi sąsiedzi są zawsze w odległości poniżej x metrów. Następnie można zastosować podobne podejście, jak w przypadku instrukcji postgis.

Twoje drugie zapytanie może zostać nieco przyspieszone. Obecnie oblicza się obszar dla każdego obiektu w tabeli 1 tak często, jak tabela zawiera wiersze - strategia najpierw łączy dane, a następnie wybiera na podstawie tej funkcji. Można zmniejszyć liczbę obliczeń strefy istotnie być precomputing zakresie:

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; 

Trzecie zapytanie może być znacznie zoptymalizowane za pomocą obwiedni: Kiedy obwiedni dwóch obiektów nie pokrywają się, nie ma sposobu, obiekty zrobić . Pozwala to na użycie danego indeksu, a tym samym ogromny wzrost wydajności.

Answer 2

Co może być konieczne jest indeksem KNN który miejmy nadzieję wkrótce dostępne w PostGIS 2.x oraz PostgreSQL 9.1: Zobacz http://blog.opengeo.org/tag/knn/

Answer 3

Od late September 2011, PostGIS wsparła indeksowane najbliższego sąsiada kwerend za pomocą specjalnego operatora (-ów) użyteczna w klauzuli ORDER BY:

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

... zwróci 10 obiektów, których geom jest najbliższy -90,40 w skalowalny sposób.Kilka dalszych szczegółów (opcji i zastrzeżeń) znajduje się w tym ogłoszeniu: post i use of the <-> i the <#> operators jest również teraz udokumentowane w oficjalnym referencji PostGIS 2.0. (Główną różnicą między nimi jest, że <-> porównuje centroidy kształt i <#> porównuje swoje granice. - nie ma znaczenia dla punktów, inne kształty wybrać to, co jest właściwe dla zapytań)

Answer 4

Zakładając, że punkt P i G wielokątów, twój oryginalne zapytanie:

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; 

Powraca k najbliższych sąsiadów w zestawie pxg. Zapytanie może wykorzystywać indeksy, ale wciąż musi zamówić cały zbiór p x g, aby znaleźć k wierszy o najmniejszej odległości. To, czego zamiast tego chcesz, to:

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;