Problema do vizinho mais próximo no Postgis 2.0 usando o índice GIST (função <->)

25

Estou tentando usar a nova função do Postgis 2.0 <-> (Geometry Distance Centroid) para calcular, para cada linha da minha tabela (cosn1), a distância do polígono mais próximo da mesma classe.

Eu estava tentando usar o seguinte código:

WITH index_query AS (
  SELECT g1.gid As ref_gid, ST_Distance(g1.the_geom,g2.the_geom) As ENN    
    FROM "cosn1" As g1, "cosn1" As g2   
    WHERE g1.gid <> g2.gid AND g1.class = g2.class
    ORDER BY g1.gid, g1.the_geom <-> g2.the_geom) 
SELECT DISTINCT ON (ref_gid) ref_gid, ENN 
    FROM index_query
ORDER BY ref_gid, ENN;

Mas então eu percebo o aviso:

Nota: O índice somente entra em ação se uma das geometrias for uma constante (não em uma subconsulta / cte). por exemplo, 'SRID = 3005; POINT (1011102 450541)' :: geometry em vez de a.geom

Significando que o Índice não será usado e a consulta levará quase o mesmo tempo que antes de usar:

SELECT DISTINCT ON(g1.gid)  g1.gid As ref_gid, ST_Distance(g1.the_geom,g2.the_geom) As ENN    
    FROM "cosn1" As g1, "cosn1" As g2   
    WHERE g1.gid <> g2.gid AND g1.class = g2.class
    ORDER BY g1.gid, ST_Distance(g1.the_geom,g2.the_geom)

Alguém pode me indicar uma solução alternativa que me permita melhorar o desempenho da minha consulta?

Muito obrigado.

nearest-neighbor postgis-2.0 Alexandre Neto
fonte
Ainda sem respostas, você pode perguntar isso na lista de discussão do PostGIS.
GIS-Jonathan
Eu já fiz, mas também sem respostas.
Alexandre Neto
3
Você pode usar g1.gid> g2.gid na cláusula where, que reduzirá o número de cálculos de distância que você precisa fazer. Infelizmente, até que o operador <-> funcione sem constantes, não veremos muita melhoria na velocidade nesse tipo de consulta.
John Powell
John, preciso manter todos os gids, mesmo aqueles que são repetidos, pois preciso atualizar o EEN para cada um dos polígonos na minha tabela "cosn1". Mas o que você disse me deu uma ideia. Eu poderia fazer o que você diz usando g1.gid> g2.gis para reduzir os cálculos de distância, mas mantendo g1.gid e g2.gid no resultado. Depois disso, eu pude unir duas subconsultas (uma com g1.gis como gid e outra com g2.gid). Obrigado
Alexandre Neto
Eu descobri que uma solução possível para solucionar o problema constante seria usar o <-> dentro de uma função SQL, usando the_geom como parâmetro. Fiz alguns testes e, em alguns casos, é muito mais rápido (). Mas no meu caso, como as distâncias estão dentro da mesma tabela, muitos cálculos de distância são repetidos durante o processo, tornando-o mais lento do que usando a consulta direta.
Alexandre Neto

Respostas:

2

Hum fazendo alguns testes na minha máquina parecia que este operador <-> não está funcionando corretamente. Não tenho certeza de que seja um bug, mas ele relatou distância zero em geometrias não sobrepostas. Intrigante, não?

Bem, e as otimizações tradicionais tradicionais de consulta SQL? Como esses resultados inesperados com o operador <->, substituo-o por st_centroid. Obteve resultados muito melhores em velocidade.

Espero que a semântica com st_overlaps continue a mesma. Pelo menos isso foi compreendido na documentação sobre <->

Dos documentos no Postigs <->

Para outros tipos de geometria, a distância entre os centróides da caixa delimitadora de ponto flutuante é retornada.

Nos meus dados de teste com ~ 5.5k polígonos, a velocidade aumentou de ~ 1000 segundos para ~ 5 segundos sem indexação espacial.

Enfim, por que usar o DISTINCT ON para fazer agrupamentos? Vejo algumas pessoas usando, mas o grupo não existe para eliminar duplicatas?

Sua consulta com otimizações SQL padrão sem o erro st_centroid introduzido

select g1.gid, min( st_distance( g1.the_geom, g2.the_geom ) ) AS enn
FROM 
  "cosn1" AS g1, "cosn1" AS g2
WHERE
  g1.gid <> g2.gid
  AND g1.class = g2.class
  AND g1.the_geom && g2.the_geom
GROUP BY
  g1.gid

Feliz feriado de natal!

cavila
fonte
Desculpe, mas sua resposta não resolve o problema. Na verdade, é muito mais rápido, mas os resultados não são precisos, pois o resultado final é calculado usando os centróides dos polígonos, em vez de sua geometria real. O <-> visa otimizar a busca de candidatos ao vizinho mais próximo, mas no final deve usar as geometrias reais para calcular a distância dos melhores candidatos. Também tentei usar o MIN \ GROUP BY em vez do DISTINCT ON \ ORDER BY e parece mais lento.
Alexandre Neto
Mas o manual postgis para o operador <-> afirma que ele usa o centróide para geometrias não pontuais. Portanto, minha solução forneceria resultados semelhantes. Deverá fornecer os mesmos resultados que sua consulta principal. Verifique se os resultados com o operador <-> também estão corretos. Ele me relatou geometrias de comprimento zero nos meus dados de teste para que os resultados pudessem ser quebrados e essa solução forneceu dados mais precisos. Se você conseguir publicar alguns registros de amostra mostrando erros em algum site de pastéis, poderemos descobrir falhas na solução.
Cavila
Se você marcar minha consulta, o operador <-> seria usado apenas para solicitar os candidatos, o resultado final é calculado usando as geometrias reais. De qualquer forma, como eu disse antes, o <-> aumento de desempenho só funciona com pontos fixos. Essa foi a minha pergunta original.
Alexandre Neto
Então, você concorda que a consulta superior não é equivalente à consulta inferior? Como a ordem mudará porque o operador <-> ORDER BY st_centroid e a st_distance fornecerão um valor diferente? Uma ordem diferente pode trazer uma consulta diferente como a primeira linha a transmitir na cláusula DISTINCT ON? A consulta válida seria a parte inferior que precisa melhorar a velocidade?
Cavila
Sim, a primeira consulta é uma intenção de melhorar a velocidade na parte inferior. E sim, pode dar um resultado um pouco diferente, já que g1.geom <-> g2.geom usa os centróides, e isso significa que a primeira linha pode não estar mais próxima. Para fazê-lo funcionar, acredito que teria que colocar um limite na ordem por cláusula, digamos, limite 10 e depois extrair os valores reais da distância. Poderia até usar o <#>, que usa as caixas delimitadoras, em vez dos centróides.
Alexandre Neto