¿Hay alguna forma de usar un almacén de valores clave para datos geoespaciales?

He usado muchas bases de datos relacionales en el pasado, pero también he leído sobre todas las bases de datos NoSQL, y las tiendas Key-Value parecen interesantes.

Cuando almaceno objetos geométricos, utilizo principalmente cinco columnas indexadas ID, MIN_X, MAX_X, MIN_Y y MAX_Y (donde X e Y están en una proyección de mapa). No necesito un índice en mis otros datos.

Necesito los valores X e Y para buscar objetos en un lugar específico (rectángulo del mapa), y necesito el valor de ID si quiero actualizar un objeto específico.

¿Hay alguna manera de que pueda usar una tienda Key-Value para esto?

Utilizamos Google AppEngine para ejecutar consultas espaciales / de atributos y el problema principal (desde el primer día) es cómo indexar grandes conjuntos de líneas / polígonos de tamaño arbitrario. Los datos de puntos no son demasiado difíciles (ver geohash, geomodel, etc.) pero los conjuntos de polígonos pequeños / grandes agrupados aleatoriamente siempre fueron un problema (y en algunos casos, todavía lo son)

He probado varias versiones diferentes de indexación espacial en GAE, pero la mayoría son solo variantes de dos a continuación. Ninguno era tan rápido como las bases de datos SQL y todos tienen pros / contras. Sin embargo, las compensaciones parecen razonables para la mayoría de las aplicaciones de mapeo basadas en Internet. Además, los dos siguientes deben combinarse con la eliminación de geometría en memoria (a través de JTS, etc.) para eliminar cualquier característica que no se ajuste a los parámetros de búsqueda finales. y finalmente, confían en las características específicas de GAE, pero estoy seguro de que podría aplicarse a otras arquitecturas (o usar TyphoonAE para ejecutarse en un clúster de Linux, ec2, etc.)

Cuadrículas : empaque todas las características de un área determinada en un índice de cuadrícula conocido. Coloque un pequeño índice espacial en la cuadrícula para navegar rápidamente por el conjunto de características que contiene. Para la mayoría de las consultas, solo necesitará extraer un puñado de cuadrículas, lo que es rápido, ya que conoce la convención de nomenclatura exacta de la cuadrícula y cómo se relaciona con las entidades K / V (obtiene, no consultas)

Pros : bastante rápido, fácil de implementar, sin huella de memoria.

Contras : se necesita un preprocesamiento, el usuario debe decidir el tamaño de la cuadrícula, las grandes geoms se comparten en varias cuadrículas, el agrupamiento puede hacer que las cuadrículas se sobrecarguen, los costos de serialización / deserialización pueden ser un problema (incluso cuando se comprimen a través de buffers de protocolo)

QuadKeys : esta es la implementación actual. básicamente es lo mismo que las cuadrículas, excepto que no hay un nivel de cuadrícula establecido. A medida que se agregan características, son indexadas por la cuadrícula de quadkey que contiene completamente sus límites (o, en algunos casos, se dividen en dos cuando no se puede usar un solo quadkey, piense en la línea de fecha). Después de encontrar el qk, se divide en un número máximo de qk más pequeños que proporcionan representaciones de grano más finas de la característica. un puntero / bbox a esa característica se empaqueta en un índice de cuadrícula liviano (grupo de características) que se puede consultar (un diseño original consultaba las características directamente, pero esto resultó demasiado lento / CPU intensivo en los casos en que el conjunto de resultados era grande)

Polyline Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_1.png Polygon Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_2.png

La convención de nomenclatura de quadkey utilizada anteriormente es bien conocida y, lo que es más importante, tiende a preservar la localidad (se describe más aquí )

El polígono de arriba se parece a esto: 0320101013123 03201010131212 03201010131213 0320101013132 0320101013133 03201010131302 03201010131303 032010101313002 032010101313003 03201010131131312 032010101313013 0320101010131313 032010101010131312 032010101313013 0320101010131312 032010101313013

Si los límites de la consulta son lo suficientemente pequeños, puede buscarlos directamente a través de qk. Esto es óptimo, ya que es solo una sola llamada RPC por lotes al almacén de datos GAE. si los límites son lo suficientemente grandes como para incluir demasiados qks posibles (> 1000), puede consultar alternativamente con un filtro (por ejemplo: qk> = 0320101013 y qk <= 0320101013 + \ ufffd). La convención de nomenclatura quadkey más la forma en que GAE indexa las cadenas permite que la consulta anterior recupere solo las cuadrículas existentes que caen por debajo de ese valor qk.

Hay otras advertencias y problemas de rendimiento, pero en general, es la capacidad de consultar en los quadkeys lo que lo hace factible.

ejemplos: consulta en condados de EE. UU . : geojson

Pros : bastante rápido, sin configuración de tamaño de cuadrícula, sin huella de memoria, sin cuadrículas superpobladas

Contras : se necesita preprocesamiento, posible sobrecarga en algunos escenarios, sin datos polares

Curvas de relleno espacial : eche un vistazo a la charla de Alfred NextGen Queries en Google I / O este año. La inclusión de curvas de relleno de espacio / tiempo genéricas junto con los nuevos operadores MultiQuery (ejecutados en paralelo) permitirá algunas consultas espaciales realmente geniales. ¿Va a superar el rendimiento tradicional de SQL? Difícil de decir pero debería escalar muy bien. Y nos estamos acercando rápidamente a un futuro en el que los dispositivos móviles siempre activos de todas las formas / tamaños aumentarán drásticamente el tráfico a su sitio / servicio.

Finalmente, también estaría de acuerdo en que debe observar muy de cerca su dominio problemático antes de elegir NoSQL sobre SQL. En nuestro caso, me gustó mucho el modelo de precios de GAE, por lo que realmente no había otra opción, pero si no necesita escalar, ahorre algo de tiempo y simplemente use un sql db estándar

He oído hablar de GeoCouch, que es una implementación de CouchDB para datos basados ​​en la ubicación. Y también creo que MongoDB tiene capacidades de indexación geoespacial.

Esta es principalmente una pregunta sobre algoritmos. Stack Overflow también puede ser un buen lugar para preguntarlo.

En cualquier caso, la respuesta a su pregunta directa es "sí, puede usar una tienda kvp para representar datos espaciales". Una mejor pregunta, sin embargo, podría ser "¿DEBO usar una tienda kvp para representar datos espaciales?"

La respuesta a esa pregunta (como muchas otras) es "depende". Depende de su escala, su carga de trabajo (transaccional), la naturaleza de los datos y la infraestructura computacional que tiene a su disposición.

Una tienda de kvp tendrá una sobrecarga baja, lo que puede ayudar a aumentar el rendimiento para grandes volúmenes de paralelismo de inserción y actualización. Sin embargo, no será muy rápido realizar búsquedas espaciales (encontrar todos los objetos dentro de un rectángulo). Para eso querrías un índice espacial, como un R-Tree.

Sin embargo, si tiene un volumen de datos realmente grande y un gran grupo de computadoras, el uso de un índice kvp podría proporcionar algunos beneficios de rendimiento. La única forma de saber realmente con certeza es tomar medidas de rendimiento utilizando los datos reales y acceder a los patrones que espera encontrar.

Actualización :

Aquí hay un poco más de información. Puede usar una tienda KVP para realizar búsquedas espaciales. El problema es que es lento. Para ver por qué, considere algo como esto:

  ***********
  ***********
  ***********
  ***********
  ****###****
  ****###****
  ****###****
  ***********
  ***********
  ***********
  ***********

Donde * y # representan objetos, dispuestos en una cuadrícula de 11x11, con el origen en la esquina superior izquierda. Imagine una búsqueda de objetos dentro del rectángulo (4,4) - (7,7). Eso debería encontrar todos los "#". Suponiendo que está utilizando un árbol b + para representar sus índices en el almacén KVP, puede encontrar los resultados utilizando el índice "X" o el índice "Y". En este caso, no importa cuál. En aras de la discusión, usaré el índice x. Haría una búsqueda de registro (n) en el índice X para encontrar el primer nodo con un valor X de "4" y luego iterar a través de los nodos hoja b + -tree hasta encontrar un nodo con un valor mayor que 7. A medida que iterar a través del índice x luego rechazaría cualquier cosa que estuviera fuera del rango y deseado.

Esto es lento Imagínelo en una cuadrícula grande, con la misma densidad, digamos 100 K * 100 K. Allí terminaría escaneando "300, 000" entradas de índice para encontrar solo 9 registros. Sin embargo, si utiliza un R-Tree correctamente equilibrado, entonces la búsqueda del índice probablemente solo necesite escanear unos 90 registros más o menos. Esa es una gran diferencia.

Sin embargo, el problema es que mantener un R-Tree equilibrado es costoso. Es por eso que la respuesta es "depende", y por qué la pregunta "¿debería hacer esto?" Es mucho más importante que "cómo lo hago".

Si inserta y elimina muchos registros, y en su mayoría realiza una búsqueda de "ID de objeto", y no realiza con frecuencia la búsqueda "espacial", entonces el uso de su índice KVP le dará un mejor rendimiento para lo que realmente quiere usar el sistema . Sin embargo, si inserta o elimina con poca frecuencia, pero realiza muchas búsquedas espaciales, entonces desea utilizar un R-Tree.

Si usa valores lat / long, es posible que pueda usar geohashes como parte del valor de su tienda.

Aquí hay uno para Nueva York. dr5regy6rc6ye

Con el geohash, puede comenzar a eliminar caracteres al final del geohash para obtener una cuadrícula de precisión variable: http://geohash.org/dr5re

Ejemplo de implementación js: http://github.com/davetroy/geohash-js

En la mayoría de los casos, obtendrá más utilidad del almacenamiento de datos relacionales que del almacenamiento de clave / valor o clave / valor / tipo. Existen considerables complejidades en torno a consultas e informes eficientes sobre este tipo de esquema de datos.

Mi consejo sería evaluar de cerca si su báscula realmente requiere NoSQL antes de considerar cómo usarla.

Eche un vistazo a esta aplicación GAE que serializa la geometría JTS en BigTable . Es posible que pueda adoptarlo para otros motores de almacenamiento NoSQL .

MongoDB tiene la facilidad de crear y consumir índices geoespaciales basados ​​en estrictas propiedades de tupla 2d [x, y] de Documentos, y permite consultas de tipo 'cerca' y 'límites'. Sin embargo, no maneja ninguna corrección para las proyecciones y utiliza un modelo idealizado de una tierra plana.

Usaría las tiendas de clave / valor solo como una capa de almacenamiento en caché, consulte http://www.membase.org/ o http://wiki.basho.com/display/RIAK/How+Things+Work (riak_kv_cache_backend)

Dependiendo de las necesidades de su aplicación, es posible que desee tener acceso SQL a los datos.

Este es ciertamente un área de interés emergente, algunas próximas charlas de la conferencia FOSS4G :

• GeoCouch: un índice espacial para CouchDB
• Indexación geoespacial con MongoDB
• Más allá de PostGIS
• Indexación espacial distribuida en la nube