K-interrogation du voisin le plus proche dans PostGIS
j'utilise la requête suivante du plus proche voisin dans 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;
maintenant, que j'ai créé des index sur le_geom aussi bien que la colonne gid sur les deux tables, cette requête prend beaucoup plus de temps que d'autres requêtes spatiales impliquant des jointures spatiales B/w deux tables.
y a-t-il un meilleur moyen de trouver les voisins les plus proches? Je suis à l'aide de PostGIS.
et, une autre requête qui prend un temps inhabituellement long malgré la création des index sur la colonne de géométrie est:
select g1.gid , g2.gid from polygons as g1 , polygons as g2
where st_area(g1.the_geom) > st_area(g2.the_geom) ;
je crois, ces requêtes ne sont pas bénéficié de l'essentiel des indices, mais pourquoi?
alors que cette requête:
select a.polyid , sum(length(b.the_geom)) from polygon as a , roads as b
where st_intersects(a.the_geom , b.the_geom);
Les retours se produisent après un certain temps malgré la présence d'une table "roads" qui est beaucoup plus grande que la table polygones ou points et qui implique aussi des opérateurs spatiaux plus complexes.
5 réponses
Juste quelques pensées sur votre problème:
st_distance ainsi que st_area ne peuvent pas utiliser d'indices. C'est parce que les deux fonctions ne peuvent pas être réduites à des questions comme "est a dans b?"ou" est-ce que a et b se chevauchent?". Encore plus concret: GIST-indices ne peut fonctionner que sur les boîtes de limite de deux objets.
pour plus d'informations sur ce que vous pouvez juste regarder dans le manuel postgis, qui indique un exemple avec st_distance et comment la requête peut être amélioré pour mieux performer.
cependant, cela ne résout pas votre problème de K-plus-proche-voisin. Pour ça, maintenant je n'ai pas une bonne idée de comment améliorer les performances de la requête. La seule chance que je vois serait de supposer que les K voisins les plus proches sont toujours à une distance de moins de x mètres. Vous pouvez alors utiliser une approche similaire à celle utilisée dans le manuel postgis.
votre deuxième requête pourrait être un peu accélérée. Actuellement, vous calculez la zone pour chaque objet dans tableau 1 aussi souvent que le tableau a des lignes - la stratégie est d'abord de joindre les données, puis de sélectionner en fonction de cette fonction. Vous pouvez réduire le nombre de calculs de surface de manière significative précomputer la zone:
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;
votre troisième requête peut être optimisée de manière significative en utilisant des boîtes de limites: lorsque les boîtes de limites de deux objets ne se chevauchent pas, il n'y a pas moyen que les objets le fassent. Cela permet l'utilisation d'un indice et donc un énorme gain de performance.
Depuis fin septembre 2011, PostGIS a pris en charge les requêtes indexées du plus proche voisin via un (des) opérateur (s) Spécial (s) utilisable (s) dans l'ordre Par clause:
SELECT name, gid
FROM geonames
ORDER BY geom <-> st_setsrid(st_makepoint(-90,40),4326)
LIMIT 10;
...retournera les 10 objets dont geom est le plus proche -90,40 d'une manière évolutive. Quelques détails supplémentaires (options et mises en garde) se trouvent dans cette annonce post et utilisation de la <-> et le <#> les opérateurs est aussi maintenant documentée dans la référence officielle PostGIS 2.0. (La principale différence entre les deux est que <-> compare les centroïdes de forme et <#> compare leurs limites - aucune différence pour les points, d'autres formes choisir ce qui est approprié pour vos requêtes.)
ce dont vous pourriez avoir besoin est L'index KNN qui sera disponible prochainement dans PostGIS 2.X et PostgreSQL 9.1: voirhttp://blog.opengeo.org/tag/knn/
en supposant que vous avez p point et G polygones, votre requête 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;
renvoie les K voisins les plus proches dans le jeu p x G. La requête peut utiliser des index, mais elle doit tout de même ordonner l'ensemble p x g pour trouver les lignes k avec la plus petite distance. Ce que vous voulez est la suivante:
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;
Vous pouvez le faire avec L'index KNN et la jointure latérale.
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