K-Nearest Neighbor Query in PostGIS

Question

Sto usando il seguente 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; 

Ora, che ho creato indici su the_geom così come colonna gid su entrambi i tavoli, questa query è richiede molto più tempo di altre query spaziali che coinvolgono join spaziali in bianco e nero due tabelle.

C'è un modo migliore per trovare i vicini più vicini a K? Sto usando PostGIS.

E, un'altra domanda che sta prendendo un tempo insolitamente lungo, nonostante la creazione di indici sulla colonna di geometria è:

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

credo, queste query arent beneficiato di indici GIST, ma perché?

considerando che la presente interrogazione:

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

restituisce il risultato dopo un certo tempo, nonostante che coinvolge "strade" da tavolo che è molto più grande di poligoni o punti tavolo e coinvolgono anche gli operatori spaziali più complesse.

Answer 1

A pochi pensieri sul vostro problema:

ST_Distance così come ST_Area non sono in grado di utilizzare gli indici. Questo perché entrambe le funzioni non possono essere ridotte a domande come "Is a within b?" oppure "A a b si sovrappongono?". Ancora più concreto: gli indici GIST possono operare solo sui riquadri di delimitazione di due oggetti.

Per ulteriori informazioni su questo, è sufficiente guardare nello postgis manual, che riporta un esempio con st_distance e in che modo la query potrebbe essere migliorata per offrire prestazioni migliori.

Tuttavia, questo non risolve il problema k-next-neighbor-neighbor. Per quello, in questo momento non ho una buona idea di come migliorare le prestazioni della query. L'unica possibilità che vedo presuppone che i k vicini più vicini siano sempre in una distanza inferiore a x metri. Quindi potresti usare un approccio simile a quello fatto nel manuale postgis.

La tua seconda query potrebbe essere accelerata un po '. Attualmente, calcoli l'area per ogni oggetto nella tabella 1 tutte le volte che la tabella contiene righe: la strategia è prima di unire i dati e quindi selezionare in base a tale funzione. Si potrebbe ridurre il numero di calcoli dell'area essere significativamente precomputing zona:

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; 

vostra terza query può essere notevolmente ottimizzato utilizzando le caselle di delimitazione: Quando i riquadri di delimitazione di due oggetti non si sovrappongono, non v'è alcun modo in cui gli oggetti fanno . Ciò consente l'utilizzo di un dato indice e quindi un enorme guadagno in termini di prestazioni.

Answer 2

Cosa potrebbe essere necessario è l'indice KNN, che si spera presto disponibile in PostGIS 2.xe PostgreSQL 9.1: Vedere http://blog.opengeo.org/tag/knn/

Answer 3

Dal late September 2011, PostGIS ha sostenuto le query più vicine indicizzati vicini tramite un operatore di speciale (s) utilizzabile nella clausola ORDER BY:

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

... restituirà i 10 oggetti la cui geom è più vicino -90,40 in modo scalabile.Alcuni ulteriori dettagli (opzioni e avvertenze) presenti in quell'annuncio post e use of the <-> e the <#> operators sono ora documentati nel riferimento PostGIS 2.0 ufficiale. (La differenza principale tra i due è che <-> confronta i baricentri forma e <#> confronta i loro limiti -. Nessuna differenza per i punti, le altre forme scegliere ciò che è appropriato per le vostre domande)

Answer 4

Supponendo di avere poligoni punto P e G, la vostra query originale:

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; 

Sta restituendo i k vicini più vicini nel set di pxg. La query potrebbe utilizzare indici, ma deve ancora ordinare l'intero p x g set per trovare le k righe con la distanza più piccola. Quello che invece vuoi è il seguente:

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;