Me gustaría saber qué sugieren las personas como formas eficientes de realizar una consulta espacial en Amazon Web Services SimpleDB?Consultas espaciales en AWS SimpleDB
Por consulta espacial me refiero a encontrar objetos en un radio dado de latitud y longitud.
SimpleDB no ofrece actualmente ninguna operación de búsqueda espacial incorporada, pero eso no significa que no se pueda realizar. Hay varios métodos para implementar búsquedas geoespaciales en bases de datos no geoespaciales como SimpleDB y todas ellas se centran en la idea de usar la base de datos para recuperar una primera selección aproximada basada en un cuadro de delimitación geoespacial y luego filtrar los datos devueltos en la aplicación usando Algoritmos más precisos como el Haversine formula.
Usted podía tienda de la latitud y longitud como atributos numéricos (con relleno de ceros y normalizado) y luego realizar una consulta de rango doble (lat >= minLat and lat <= maxLat and lon >= minLat and lon <= maxLat), pero ya que ninguno de theese predicados son selectivos (cada predicado coincide con una gran cantidad de artículos) no es ideal (ver Tuning Queries).
Una mejor manera sería usar GeoHashes.
Geohashes ofrecen propiedades como la precisión arbitraria, prefijos similares para posiciones cercanas, y la posibilidad de eliminar gradualmente caracteres desde el final del código para reducir su tamaño (y poco a poco perder precisión).
Como ejemplo práctico, la geohash 6gkzwgjzn820 decodifica a la coordenadas -25.382708 -49.265506 y, mientras que el geohash 6gkzwgjz se decodificación a -25.383 -49.266 y, y si tomamos una posición similar en la misma región, como -25.427 y -49.315, podemos ver que es codificado como 6gkzmg1w (tenga en cuenta el prefijo similar).
De http://geohash.org/site/tips.html
Con sus posiciones de elemento como GeoHashes podría utilizar el operador like para buscar un cuadro delimitador (where GeoHash like '6gkzmg1w%'), pero dado que el operador like es caro (Comparison Operators) una mejor manera sería desnormalizar los datos al almacenar cada nivel de prefijo GeoHash (cuántos dependen de la precisión de búsqueda requerida) como un atributo separado (GeoHash6 GeoHash8, etc.) y luego usar un predicado de igualdad simple (where Geohash8 = '6gkzmg1w').
Ahora a la desventaja de GeoHashes. Como no puede suponer que GeoHash esté centrado en su cuadro de búsqueda, también debe buscar todos los prefijos vecinos. El proceso se describe de manera excelente por geohash-js
geohash también tiene la propiedad de que como el número de dígitos disminuye (desde la derecha), la precisión se degrada. Esta propiedad se puede usar para hacer búsquedas de cuadro delimitador , ya que los puntos cercanos compartirán prefijos Geohash similares.
Sin embargo, debido a que un punto dado puede aparecer en el borde de un cuadro delimitador geohash dado, es necesario generar una lista de geohash valores con el fin de realizar una verdadera búsqueda de proximidad alrededor de un punto. Dado que el algoritmo Geohash utiliza un sistema de numeración de base 32, es posible derivar los valores de Geohash que rodean cualquier otro valor dado de Geohash usando una tabla de búsqueda simple.
Así, por ejemplo, 1600 Pennsylvania Avenue, Washington DC, resuelve: 38.897, -77.036
Usando el algoritmo geohash, esta latitud y longitud se convierte a: dqcjqcp84c6e
Un cuadro delimitador sencilla alrededor de este punto podría ser descrita por truncar esta geohash a: dqcjqc
sin embargo, 'dqcjqcp84c6e' no está centrado dentro de 'dqcjqc', y la búsqueda dentro 'dqcjqc' puede pasar por alto algunos targe deseado ts.
Por lo tanto, en su lugar, podemos utilizar las propiedades matemáticas de Geohash para calcular rápidamente los vecinos de 'dqcjqc'; nos encontramos que son: 'dqcjqf', 'dqcjqb', 'dqcjr1', 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8'
Esto nos da un cuadro delimitador alrededor ' dqcjqcp84c6e 'aproximadamente 2km x 1.5km y permite una búsqueda en la base de datos con solo 9 teclas: SELECCIONAR * FROM tabla WHERE LEFT (geohash, 6) IN (' dqcjqc ', ' dqcjqf ',' dqcjqb ',' dqcjr1 ', 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8');
Traducido a una consulta SimpleDB que estaría where GeoHash6 in('dqcjqc', 'dqcjqf', 'dqcjqb', 'dqcjr1', 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8') y luego que va a hacer el filtrado Haversine en los resultados con el fin de obtener sólo los elementos que está dentro de su radio de búsqueda.
Voy a dejar esto aquí porque podría ser de ayuda.
Hace 14 años tratamos de hacer una tabla de búsqueda geográfica de ubicaciones dentro de un radio. Obviamente no había índices geoespaciales ni nada de eso. Literalmente, solo había SQL estándar y Oracle ... de todos modos, terminamos convirtiendo todos los lat/lng en kilómetros de un campo de plano fijo. Esencialmente lo que hacen los índices geoespaciales en estos días.
Para explicar qué es exactamente lo que hace, convierte el mundo en una superficie plana y con un poco de engaño SQL incluso puede seleccionar por radio, incluso puede obtener la distancia de los dos puntos que está seleccionando. Como también son enteros enteros crudos, las consultas son increíblemente rápidas.
Aquí está un ejemplo sencillo en PHP y un aspecto muy compleja, pero bastante fácil una vez que entienda que la consulta SQL:
excelente respuesta, gracias por la discusión sobre Geohashes – user293895