¿Existe una arquitectura para el geoprocesamiento distribuido?

24

Supongamos que tengo 50 computadoras en mi LAN. Cada computadora tiene una geodatabase para todos los polígonos de parcelas en un estado particular en los Estados Unidos.

Me gustaría escribir una tarea de geoprocesamiento que encuentre todas las parcelas valoradas sobre x $ / acre que están dentro de y pies de otra parcela que se valora a menos de z $ / acre.

Me gustaría formular y ejecutar esta consulta sin saber o preocuparme de que los datos se distribuyen en 50 computadoras. Tenga en cuenta las condiciones de los límites: también quiero que la consulta devuelva los casos en que las parcelas costosas en un estado sean casi baratas en otra.

¿Existe una arquitectura que admita este tipo de geoprocesamiento distribuido?

La arquitectura se puede describir de forma abstracta o como una implementación específica de Azure o Amazon Web Services. O, preferiblemente, como una oficina típica donde las computadoras permanecen inactivas durante la noche con abundantes licencias de escritorio de ArcGIS.

    
pregunta Kirk Kuykendall 22.10.2010 - 17:56

8 respuestas

13
  1. almacene todas sus parcelas en una base de datos central
  2. formule una cuadrícula sobre los EE. UU. hecha de cuadrados N pies en un lado, donde N es tal que el número de parcelas que caben dentro de N no soplará la memoria en uno de sus nodos
  3. cree una tabla en su base de datos con una fila por cuadrícula, una columna de identificación, una columna de geometría y una columna de estado
  4. cada nodo ejecuta un pequeño programa que
    1. encuentra la siguiente casilla sin procesar
    2. lo marca como en proceso
    3. tira de todas las parcelas ST_DWithin (cuadrado, parcela, maxfeet)
    4. hace la consulta real
    5. vuelve a escribir la respuesta de la consulta en una tabla de soluciones en la base de datos central
    6. marca el cuadrado como completo
    7. volver a 1

El caso obvio de falla es que su radio de interés en la consulta de parcelas crece lo suficiente como para que grandes porciones de su conjunto de datos sean posibles candidatos para coincidir con cada parcela.

    
respondido por el Paul Ramsey 25.10.2010 - 21:11
7

Hubo una ranura interesante en FOSS4G en septiembre en Barcelona sobre esto: enlace

Se convirtió más en un panel de discusión que en una presentación.

En la mitad de esta publicación del blog Paul Ramsey ofrece una especie de resumen a partir de eso.

    
respondido por el Nicklas Avén 22.10.2010 - 18:14
4

Quizás vea el informe técnico "ArcGIS Server in Practice Series: Large Batch Geocoding" en esri white papers .

Se trata de geocodificación, pero el proceso general de uso de un servicio de geoprocesamiento asíncrono podría ser aplicable a su caso.

    
respondido por el llcf 23.10.2010 - 00:53
3

Lo primero que debe preocuparse por este problema es qué datos se necesitan dónde y cuándo. Para hacerlo, generalmente comienzo con la versión estúpida y serial del problema.

Encuentre todas las parcelas valoradas en x $ / acre que están dentro de y pies de otra parcela que se valora en 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)
      }
    }
  }
}

Si bien este algoritmo no está optimizado, solucionará el problema.

Resolví un problema similar para mi tesis de maestría que encontraba la parcela más cercana para cada punto en un conjunto de datos. Implementé la solución en PostGIS , Hadoop y MPI . La versión completa de mi tesis es aquí , pero resumiré los puntos importantes como se aplica a este problema.

MapReduce no es una buena plataforma para resolver este problema porque requiere acceso a todo el conjunto de datos (o una subconjunto seleccionado) para procesar un pecado parcela de gle. MapReduce no maneja bien los conjuntos de datos secundarios.

MPI, sin embargo, puede resolver esto muy bien. La parte más difícil es determinar cómo dividir los datos. Esta división se basa en cuántos datos hay, cuántos p Los procesadores deben ejecutarse y la cantidad de memoria que tiene por procesador. Para obtener la mejor escala (y, por lo tanto, el rendimiento), deberá tener múltiples  copias del conjunto de datos de paquetes en la memoria (en todas sus computadoras) a la vez.

Para explicar cómo funciona esto, asumiré que cada una de sus 50 computadoras tiene 8 procesadores. Luego le asigno a cada computadora la responsabilidad de verificar 1/50 de las parcelas. Esta verificación se ejecutará mediante 8 procesos en la computadora, cada uno de los cuales tiene una copia de la misma 1/50 parte de las parcelas y 1/8 de la paquete de datos de la parcela. Tenga en cuenta que los grupos no se limitan a una sola máquina, sino que pueden cruzar los límites de la máquina.

El proceso ejecutará el algoritmo, obteniendo las parcelas para p del conjunto 1/50 de parcelas, y las parcelas para q del conjunto 1/8. Despues de lo interno En bucle, todos los procesos en la misma computadora hablarán juntos para determinar si se debe emitir el paquete.

Implementé un algoritmo similar a este para mi problema. Puede encontrar la fuente aquí .

Incluso con este tipo de algoritmo no optimizado, pude obtener resultados impresionantes que fueron altamente optimizados para el tiempo del programador (lo que significa que podría escribir un algoritmo estúpido simple y el cálculo aún sería lo suficientemente rápido). El siguiente punto para optimizar (si realmente lo necesita) es configurar un índice de quadtree del segundo conjunto de datos (de donde obtiene q) para cada proceso.

Para responder a la pregunta original. Hay una arquitectura: MPI + GEOS. Agregue un poco de ayuda de mi implementación de ClusterGIS y se puede hacer bastante. Todo este software se puede encontrar como código abierto, por lo que no hay costos de licencia. No estoy seguro de qué tan portátil es para Windows (tal vez con Cygwin), ya que trabajé en Linux. Esta solución se puede implementar en EC2, Rackspace o en cualquier nube que esté disponible. Cuando lo desarrollé, estaba usando un clúster de cómputo dedicado en una universidad.

    
respondido por el Nathan Kerr 26.10.2010 - 18:34
2

La metodología de programación paralela de la vieja escuela es simplemente almacenar un estado + las parcelas que lo tocan en cada procesador, por lo que resulta embarazosamente fácil de poner en paralelo. Pero dada la variación en el tamaño de los estados de EE. UU., Obtendría un mejor rendimiento al dividir el país en celdas de cuadrícula (nuevamente con el halo de paquetes) y enviar cada celda de cuadrícula a los procesadores que utilizan una configuración de esclavo maestro.

    
respondido por el Ian Turton 22.10.2010 - 21:59
2

Es posible que desee echar un vistazo a Appistry . Pretende permitir la migración de aplicaciones existentes a infraestructuras de nube privada. Puede haber otros proyectos con un objetivo similar: en lugar de averiguar una y otra vez para cada aplicación la parte muy compleja de desglosar y distribuir tareas al procesamiento en paralelo, cree una biblioteca o plataforma que lo haga automáticamente.

    
respondido por el matt wilkie 25.10.2010 - 18:57
2

Para este tipo de problema, usaría un marco de mapa / reducir. El marco de Appistry "en bruto" es ideal para problemas "vergonzosamente paralelos", que este está cerca. Las condiciones de borde no permiten que sea. Map / Reduce (el enfoque de Google para la computación distribuida) es excelente en este tipo de problema.

El mayor avance en Appistry desde el documento de 08 es el lanzamiento del producto CloudIQ Storage. Esto permite "s3" como instalación de almacenamiento utilizando los discos en sus servidores locales. Luego, el producto CloudIQ Engine puede habilitar servicios de alto volumen o dispersar / recopilar aplicaciones de estilo de cualquier tipo (hemos probado la escalabilidad utilizando el tiempo de ejecución de ESRI y otras bibliotecas de código abierto). Si está operando con datos basados en archivos, distribúyalos utilizando CloudIQ Storage y enrute los trabajos de procesamiento a las réplicas de archivos locales para que no tengan que moverse por la red. (por lo que cada nodo no necesita todos los datos)

Para Map / Reduce, puede colocar algo como Hadoop (marco de código abierto M / R) en CloudIQ Storage. Me gustaría ver a Hadoop para ver el problema como se describe, pero realmente necesita sumergirse, no es fácil comenzar, y M / R es un problema. También hay una distribución con soporte comercial ofrecida por Cloudera. Existe otro producto de Appistry, CloudIQ Manger, que es un buen complemento de Hadoop (Cloudera o de otro tipo) para la distribución y administración.

Comenzaría con Hadoop (sistema de archivos M / R y HDFS), y si necesita una solución escalable con mayor respaldo comercial, consulte Appistry CloudIQ Manager and Storage, junto con la distro Cloudera Hadoop.

Si desea una arquitectura más simple para tareas "vergonzosamente paralelas", también debe consultar CloudIQ Engine. (Los enfoques descritos en el documento al que Kirk hace referencia siguen siendo válidos)

    
respondido por el Scott Crawford 26.10.2010 - 16:43
1

Echa un vistazo a OGSA-DQP. "DQP permite consultar las tablas de múltiples bases de datos relacionales distribuidas, utilizando SQL, como si hubiera varias tablas en una sola base de datos" enlace

    
respondido por el aengus 16.01.2011 - 15:26

Lea otras preguntas en las etiquetas