Existe uma arquitetura para geoprocessamento distribuído?

Suponha que eu tenha 50 computadores na minha LAN. Cada computador possui um banco de dados geográfico para todos os polígonos de parcela em um estado específico nos EUA.

Eu gostaria de escrever uma tarefa de geoprocessamento que encontre todas as parcelas avaliadas em x $ / acre que estão a y pés de outra parcela avaliada em menos de z $ / acre.

Gostaria de formular e executar esta consulta sem saber ou se importar com a distribuição dos dados em 50 computadores. Lembre-se das condições de contorno: também quero que a consulta retorne casos em que parcelas caras em um estado estejam próximas a parcelas baratas em outro.

Existe uma arquitetura que suporte esse tipo de geoprocessamento distribuído?

A arquitetura pode ser descrita de forma abstrata ou como uma implementação específica para o Azure ou o Amazon Web Services. Ou, preferencialmente, como um escritório típico, onde os computadores ficam ociosos à noite com abundantes licenças de desktop ArcGIS.

1. armazene todos os seus pacotes em um banco de dados central
2. formule uma grade sobre os EUA feita de quadrados N pés de um lado, onde N é tal que o número de parcelas que se encaixam em N não exponha a memória de um de seus nós
3. crie uma tabela no seu banco de dados com uma linha por quadrado da grade, uma coluna de identificação, uma coluna de geometria e uma coluna de status
4. cada nó executa um pequeno programa que
   1. encontre a próxima praça não processada
   2. marca como em processo
   3. puxa todas as parcelas ST_DWithin (square, parcel, maxfeet)
   4. faz a consulta real
   5. escreve de volta a resposta da consulta a uma tabela de solução no banco de dados central
   6. marca o quadrado como completo
   7. retornar a 1

O caso óbvio de falha é que o seu raio de interesse na consulta de parcelas cresce o suficiente para que grandes partes do seu conjunto de dados sejam possíveis candidatos para corresponder a cada parcela.

Havia um slot interessante no FOSS4G em setembro em Barcelona sobre isso: http://2010.foss4g.org/presentations_show.php?id=3584

Tornou-se mais um painel de discussão do que uma apresentação.

No meio deste post, Paul Ramsey faz algum tipo de resumo disso.

Talvez dê uma olhada no white paper "Servidor ArcGIS na Série Prática: Geocodificação de Lotes Grandes" nos white papers da esri .

Trata-se de geocodificação, mas o processo geral de uso de um serviço de geoprocessamento assíncrono pode ser aplicável ao seu caso.

A primeira coisa a se preocupar com esse problema é quais dados são necessários, onde e quando. Para fazer isso, geralmente começo com a versão estúpida e serial do problema.

Encontre todas as parcelas no valor de x $ / acre que estão a y pés de outra parcela avaliada em menos de z $ / acre.

foreach p in parcels {
  if value(p) > x {
    foreach q in parcels {
      if (dist(p,q) <= y) and (value(q) < z) {
        emit(p)
      }
    }
  }
}

Embora esse algoritmo não seja otimizado, ele resolverá o problema.

Resolvi um problema semelhante para minha tese de mestrado, que encontrou a parcela mais próxima para cada ponto de um conjunto de dados. Eu implementei a solução no PostGIS , Hadoop e MPI . A versão completa da minha tese está aqui , mas vou resumir os pontos importantes que se aplicam a esse problema.

O MapReduce não é uma boa plataforma para resolver esse problema, pois requer acesso a todo o conjunto de dados (ou a um subconjunto cuidadosamente selecionado) para processar um único pacote. O MapReduce não lida bem com conjuntos de dados secundários.

O MPI, no entanto, pode resolver isso com bastante facilidade. A parte mais difícil é determinar como dividir os dados. Essa divisão é baseada na quantidade de dados existentes, em quantos processadores você precisa executá-los e em quanta memória você tem por processador. Para obter o melhor dimensionamento (e, portanto, desempenho), você precisará ter várias cópias do conjunto de dados das parcelas na memória (em todos os computadores) de uma só vez.

Para explicar como isso funciona, assumirei que cada um dos seus 50 computadores possui 8 processadores. Atribuirei a cada computador a responsabilidade de verificar 1/50 das parcelas. Essa verificação será executada por 8 processos no computador, cada um com uma cópia da mesma parte 1/50 das parcelas e 1/8 do conjunto de dados da parcela. Observe que os grupos não estão limitados a uma única máquina, mas podem cruzar os limites da máquina.

O processo executará o algoritmo, obtendo as parcelas para p do conjunto 1/50 de parcelas e as parcelas para q do conjunto 1/8. Após o loop interno, todos os processos no mesmo computador conversarão juntos para determinar se a parcela deve ser emitida.

Eu implementei um algoritmo semelhante a este para o meu problema. Você pode encontrar a fonte aqui .

Mesmo com esse tipo de algoritmo não otimizado, eu era capaz de obter resultados impressionantes altamente otimizados para o tempo do programador (o que significa que eu poderia escrever um algoritmo simples estúpido e a computação ainda seria rápida o suficiente). O próximo ponto a otimizar (se você realmente precisar) é configurar um índice quadtree do segundo conjunto de dados (de onde você obtém q) para cada processo.

Para responder à pergunta original. Existe uma arquitetura: MPI + GEOS. Dê uma pequena ajuda da minha implementação do ClusterGIS e muito pode ser feito. Todo esse software pode ser encontrado como código aberto, sem taxas de licenciamento. Não tenho certeza de como é portátil para o Windows (talvez com Cygwin), pois trabalhei nele no Linux. Esta solução pode ser implantada no EC2, Rackspace ou em qualquer nuvem disponível. Quando o desenvolvi, estava usando um cluster de computação dedicado em uma universidade.

A metodologia de programação paralela da velha escola é apenas armazenar um estado + as parcelas que o tocam em cada processador, então é embaraçosamente fácil paralelizar. Mas, dada a variação no tamanho dos estados dos EUA, você obteria melhor desempenho dividindo o país em células da grade (novamente com o halo tocante das parcelas) e enviando cada célula da grade aos processadores usando uma configuração de escravo mestre.

Você pode dar uma olhada no Appistry . Pretende permitir a migração de aplicativos existentes para infraestruturas de nuvem privada. Pode haver outros projetos com um objetivo semelhante: em vez de descobrir repetidamente para cada aplicativo a porca muito complexa de decompor e distribuir tarefas para processamento paralelo, crie uma biblioteca ou plataforma que faça isso automaticamente.

Para esse tipo de problema, eu usaria uma estrutura de mapa / redução. A estrutura Appistry "bruta" é ótima para problemas "embaraçosamente paralelos", dos quais este se aproxima. As condições da borda não permitem que seja. Mapear / Reduzir (a abordagem do Google para a computação distribuída) é ótimo nesse tipo de problema.

O maior avanço na Appistry desde o artigo 08 é o lançamento do produto CloudIQ Storage. Isso permite o recurso de armazenamento "s3", utilizando os discos nos servidores locais. Em seguida, o produto CloudIQ Engine pode habilitar serviços de alto volume ou aplicativos de estilo de dispersão / coleta de qualquer tipo (comprovamos a escalabilidade usando o tempo de execução ESRI e outras bibliotecas de código aberto). Se você estiver operando com dados baseados em arquivos, distribua-os usando o CloudIQ Storage e roteie os trabalhos de processamento para as réplicas de arquivos locais, para que eles não precisem ser movidos pela rede. (para que cada nó não precise de todos os dados)

Para Mapear / Reduzir, é possível colocar em camadas algo como o Hadoop (estrutura M / R de código aberto) no CloudIQ Storage. Eu procuraria no Hadoop o problema conforme descrito, mas você realmente precisa se aprofundar, não é fácil começar, e o M / R é um dobrador de cérebros. Há também uma distribuição comercialmente suportada oferecida pela Cloudera. Há outro produto Appistry, o CloudIQ Manger, que é um ótimo complemento para o Hadoop (Cloudera ou não) para distribuição e gerenciamento.

Eu começaria com o Hadoop (sistema de arquivos M / R e HDFS) e, se você precisar de uma solução escalável com suporte comercial, consulte o Appistry CloudIQ Manager and Storage, em conjunto com a distribuição Cloudera Hadoop.

Se você deseja uma arquitetura mais simples para tarefas "embaraçosamente paralelas", consulte também o CloudIQ Engine. (as abordagens descritas no artigo de Kirk ainda são válidas)

Dê uma olhada no OGSA-DQP. "O DQP permite que as tabelas de vários bancos de dados relacionais distribuídos sejam consultadas, usando SQL, como se houvesse várias tabelas em um único banco de dados" http://ogsa-dai.sourceforge.net/documentation/ogsadai4.0/ogsadai4.0- axis / DQPOverview.html