La primera cosa que se preocupa con este problema es lo que se necesitan los datos de donde y cuando. Para ello, por lo general comienzan con el estúpido de serie de la versión del problema.
Encontrar todos los paquetes valorados en más de $x/acre que están dentro y los pies de otra parcela en la que está valorado 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)
}
}
}
}
Mientras que este algoritmo no está optimizado, se va a resolver el problema.
He resuelto un problema similar para mi tesis de Maestría que se encuentra la más cercana a la parcela por cada punto en un conjunto de datos. He implementado la solución en PostGIS, Hadoop
y MPI. La versión completa de mi tesis es aquí, pero voy a resumir los puntos importantes ya que se aplica a este problema.
MapReduce no es una buena plataforma para resolver este problema, ya que requiere el acceso a todo el conjunto de datos (o una cuidadosamente seleccionada subconjunto) para procesar un pecado
gle parcela. MapReduce no controla secundaria conjuntos de datos.
MPI, sin embargo, puede resolver muy fácilmente. La parte más difícil es determinar cómo dividir los datos. Esta división se basa en la cantidad de datos que hay, cómo muchos p
rocessors tiene que ejecutar, y cuánto de memoria por procesador. Para la mejor escala (y por lo tanto el rendimiento), es necesario tener varios
copias de las parcelas del conjunto de datos en la memoria (a través de todos los ordenadores) a la vez.
Para explicar cómo funciona esto, voy a suponer que cada una de las 50 computadoras tiene 8 procesadores. A continuación, voy a asignar a cada equipo la responsabilidad de revisar los 1/50
de las parcelas. Esta comprobación será ejecutado por 8 procesos en el equipo, cada uno de los cuales tiene una copia de la misma 1/50 parte de las parcelas y 1/8 de la
parcela conjunto de datos. Por favor, tenga en cuenta que los grupos no se limitan a una sola máquina, pero puede cruzar la máquina de fronteras.
El proceso se va a ejecutar el algoritmo, obteniendo las parcelas p a partir de la 1/50th conjunto de parcelas, y las parcelas para q desde el 1/8 de conjunto. Después de que el interior
bucle, todos los procesos en el mismo equipo va a hablar juntos para determinar si el paquete debe ser emitida.
He implementado un algoritmo similar a este para mi problema. Usted puede encontrar la fuente aquí.
Incluso con este tipo de no-algoritmo optimizado que yo era capaz de obtener impresionantes resultados que fueron muy optimizado para el programador de tiempo (lo que significa que podría escribir un estúpido algoritmo simple y el cálculo sería todavía lo suficientemente rápido). El siguiente punto a optimizar (si realmente lo necesita), es la instalación de un quadtree índice del segundo conjunto de datos (donde se obtiene q) para cada proceso.
Para responder a la pregunta original. Existe una arquitectura: MPI + GEOS. El tiro en un poco de ayuda de mis ClusterGIS aplicación, y mucho se puede hacer. Todo este software se puede encontrar como de código abierto, por lo que no pago de licencias. No estoy seguro de cómo portátil para Windows es (tal vez con Cygwin) como trabajé en linux. Esta solución se puede implementar en EC2, Rackspace, o lo que sea en la nube está disponible. Cuando yo se desarrolló yo estaba usando un dedicado compute cluster en una Universidad.
