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

26

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 de Key-Value parecen interresting.

Cuando almaceno un objeto geométrico, en su mayoría utilizo 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 un almacén de Key-Value para esto?

    
pregunta Jonas 22.07.2010 - 22:03

9 respuestas

18

Usamos 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 (consulte 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 es)

He probado varias versiones diferentes de indexación espacial en GAE, pero la mayoría son solo variantes de las dos a continuación. Ninguno fue tan rápido como las bases de datos SQL y todos tienen ventajas y desventajas. Sin embargo, las compensaciones parecen razonables para la mayoría de las aplicaciones de mapas basadas en Internet. Además, los dos a continuación deben combinarse con la selección de geometrías 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, dependen de 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 : reúne todas las funciones para 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 tendrá que extraer un puñado de cuadrículas, lo que es rápido, ya que conoce la convención exacta de nomenclatura de cuadrícula y cómo se relaciona con las entidades K / V (obtiene, no las consultas)

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

Contras : es necesario realizar un preprocesamiento, el usuario debe decidir el tamaño de la cuadrícula, se comparten grandes geoms en varias cuadrículas, la agrupación en clústeres puede sobrecargar las redes, los costos de serialización / deserialización pueden ser un problema (incluso cuando comprimido a través de búferes de protocolo)

QuadKeys : esta es la implementación actual. básicamente es lo mismo que Grids, excepto que no hay un nivel de grilla establecido. a medida que se agregan funciones, se indexan por la cuadrícula de cuatro teclas que contiene completamente sus límites (o, en algunos casos, se dividen en dos cuando no se puede usar una sola tecla, piense en la línea de datos). Una vez que se encuentra el qk, luego se divide en un número máximo de qk más pequeños que proporcionan representaciones de grano más fino de la característica. un puntero / bbox a esa característica se empaqueta en un gridindex ligero (grupo de características) que puede ser consultado (un diseño original consultó las características directamente pero esto resultó demasiado lento / CPU intensivo en casos donde el conjunto de resultados fue grande)

Quadkeys de polilínea http://www.arc2earth.com/images/help/GAE_QKS_1.png Quadkeys de polígonos http://www.arc2earth.com/images/help/GAE_QKS_2.png

La convención de nomenclatura de cuatro teclas 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 ve así: 0320101013123 03201010131212 03201010131213 0320101013132 0320101013133 03201010131302 03201010131303 032010101313002 032010101313003 032010101313012 032010101313013 03201010131312 03201010131313 032010101313102 ...

si los límites de la consulta son lo suficientemente pequeños, puede obtener directamente a través del qk. esto es óptimo, ya que solo es una llamada de rpc por lotes única al almacén de datos GAE. Si los límites son lo suficientemente grandes como para incluir demasiados qks posibles (> 1000), también puede consultar utilizando 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 obtenga 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 las cuatro teclas lo que lo hace posible

ejemplos: consulta en los 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 : es necesario realizar un preprocesamiento, posible sobrecarga en algunos escenarios, sin datos polares

Curvas de relleno de espacio : eche un vistazo a Charla sobre consultas de Alfred's NextGen 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 interesantes. ¿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 encendidos de todas las formas y tamaños aumentarán drásticamente el tráfico a su sitio / servicio.

por último, también estoy de acuerdo en que deberías mirar muy de cerca tu dominio de problemas 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, ahórrese tiempo y solo use una base de datos estándar de SQL

    
respondido por el bFlood 30.07.2010 - 18:58
11

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.

    
respondido por el JoshFinnie 23.07.2010 - 00:03
8

Esto es principalmente una pregunta sobre algoritmos. Desbordamiento de pila también puede ser un buen lugar para preguntar.

En cualquier caso, la respuesta a tu pregunta directa es "sí, puedes usar un almacén de kvp para representar datos espaciales". Una pregunta mejor, sin embargo, podría ser "¿DEBERÍA 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 altos volúmenes de inserción y actualización de paralelismo. 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 enorme grupo de computadoras, el uso de un índice de kvp podría proporcionar algunos beneficios de rendimiento. La única forma de saberlo con certeza es tomar medidas de perfección utilizando los datos reales y los patrones de acceso que espera encontrar.

Actualizar :

Aquí hay un poco más de información. Puedes usar una tienda KVP para hacer búsquedas espaciales. El problema es que es lento. Para ver por qué, considera 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 "#" 's. Suponiendo que está utilizando un árbol b + para representar sus índices en la tienda KVP, puede encontrar los resultados utilizando el índice "X" o el índice "Y". En este caso, no importa cuál. Por el bien de la discusión, usaré el índice x. Debería realizar 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 de hoja b + -tree hasta que encuentre un nodo con un valor mayor que 7. A medida que si recorre el índice x, rechazará todo lo que esté fuera del rango y deseado.

Esto es lento. Imagínelo en una cuadrícula grande, con la misma densidad, digamos 100 K * 100 K. Ahí tendría que escanear las entradas del índice "300, 000" para encontrar solo 9 registros. Sin embargo, si usa un R-Tree adecuadamente equilibrado, entonces la búsqueda en el índice probablemente solo necesite escanear unos 90 registros aproximadamente. Esa es una gran diferencia.

El problema, sin embargo, es que mantener un R-Tree equilibrado es costoso. Esta es la razón por la que la respuesta es "depende", y por qué la pregunta "si debo 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 hace frecuentemente la búsqueda "espacial", el uso de su índice KVP le dará un mejor rendimiento para lo que realmente desea usar El sistema para. Sin embargo, si inserta o elimina con poca frecuencia, pero realiza muchas búsquedas espaciales, entonces desea utilizar un R-Tree.

    
respondido por el Scott Wisniewski 23.07.2010 - 02:23
4

Si está usando valores de latitud / longitud, puede usar geohashes como la parte de valor de su tienda.

Aquí hay uno para NYC. dr5regy6rc6ye

Con el geohash, puedes comenzar a eliminar caracteres al final del geohash para obtener una cuadrícula de precisión variable: enlace

Ejemplo de implementación de js: enlace

    
respondido por el Jay Cummins 22.07.2010 - 22:16
1

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

Mi consejo sería evaluar detenidamente si tu escala realmente requiere NoSQL antes de considerar cómo usarla.

    
respondido por el JasonBirch 22.07.2010 - 22:16
1

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

    
respondido por el Jon Bringhurst 22.07.2010 - 22:13
1

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

    
respondido por el Chris Bray 26.07.2010 - 12:21
0

Usaré los almacenes clave / valor solo como una capa de almacenamiento en caché, consulte enlace o enlace (riak_kv_cache_backend)

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

    
respondido por el cipy 23.07.2010 - 02:18
0
respondido por el scw 13.08.2010 - 01:08

Lea otras preguntas en las etiquetas