K-Nearest Neighbor Query в PostGIS

Я использую следующий ближайший соседний запрос в 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) ;

Я считаю, что эти запросы не поддерживаются индексами gist, но почему?

В то время как этот запрос:

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

возвращает результат через некоторое время, несмотря на включение таблицы "дорог", которая намного больше, чем многоугольники или таблицы точек, а также включает более сложные пространственные операторы.

Ответы

Ответ 1

Несколько соображений по вашей проблеме:

st_distance, а также st_area не могут использовать индексы. Это связано с тем, что обе функции не могут быть сведены к таким вопросам, как "Является ли внутри b?"? или "Сделать a и b накладываться?". Еще более конкретный: GIST-индексы могут работать только на ограничивающих прямоугольниках двух объектов.

Дополнительную информацию об этом вы можете посмотреть в руководстве postgis, в котором указывается пример с st_distance и как можно улучшить запрос для улучшения работы.

Однако это не решает проблему k-ближайшего соседа. Для этого прямо сейчас у меня нет хорошей идеи, как повысить производительность запроса. Единственный шанс, который я вижу, будет предполагать, что k ближайших соседей всегда находятся на расстоянии менее х метров. Затем вы можете использовать аналогичный подход, как это сделано в руководстве 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;

Третий запрос может быть значительно оптимизирован с использованием ограничивающих полей: когда ограничивающие поля двух объектов не перекрываются, объекты не имеют никакого способа. Это позволяет использовать данный индекс и, следовательно, огромный прирост производительности.

Ответ 2

Поскольку в конце сентября 2011 года, PostGIS поддерживал индексированные запросы ближайших соседей с помощью специального оператора (-ов), который можно использовать в предложении ORDER BY:

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

... вернет 10 объектов, чей geom близок к -90,40 масштабируемым образом. Еще несколько деталей (варианты и оговорки) находятся в этом объявлении post и использование ↔ и операторов < # > также теперь описано в официальной ссылке PostGIS 2.0. (Основное различие между ними состоит в том, что <-> сравнивает центроиды формы и <#> сравнивает их границы - нет разницы для точек, другие формы выбирают то, что подходит для ваших запросов.)

Ответ 3

Вам может понадобиться индекс KNN, который, как мы надеемся, скоро появится в PostGIS 2.x и PostgreSQL 9.1: См. http://blog.opengeo.org/tag/knn/ p >

Ответ 4

Предполагая, что у вас есть p-точки и g-полигоны, ваш исходный запрос:

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;

Возвращает k ближайших соседей в наборе p x g. Запрос может использовать индексы, но он все равно должен заказать весь набор p x g, чтобы найти k строк с наименьшим расстоянием. Вместо этого вы хотите:

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;