¿Usando geohash para búsquedas de proximidad?

29

Estoy buscando optimizar el tiempo de las búsquedas geográficas de proximidad del punto.

Mi entrada es lat, lng point y estoy buscando en un conjunto de ubicaciones precalculadas a n puntos más cercanos.

No me importa cuánto tiempo / espacio tomará la creación del índice de ubicaciones precalculado, pero sí me importa que las consultas sean súper rápidas.

Estoy pensando en usar geohash como la clave de búsqueda, donde primero verificaría si obtengo resultados para X caracteres de la clave y luego continuaré recortando caracteres desde el final de la clave hasta que comience a ver los resultados.

Para mi comprensión (muy escasa por ahora) de las técnicas de índice geográfico, este enfoque debería ser capaz de producir los resultados más rápidos (en términos de tiempo de consulta) en comparación con todas las otras implementaciones conocidas (como R Tree y co.)

    
pregunta Maxim Veksler 31.12.2011 - 14:54

5 respuestas

23

Absolutamente puedes. Y puede ser bastante rápido. (Los bits de computación intensivos TAMBIÉN pueden ser distribuidos)

Hay varias formas, pero una con la que he estado trabajando es utilizando una lista ordenada de geohashes basados en enteros y encontrando todos los rangos de geohash vecinos más cercanos para una resolución de geohash específica (la resolución se aproxima a los criterios de distance ) y luego consulta esos rangos de geohash para obtener una lista de puntos cercanos. Yo uso redis y nodejs (es decir, javascript) para esto. Redis es super rápido y puede recuperar rangos ordenados muy rápidamente, pero no puede hacer muchas de las tareas de manipulación de consultas de indexación que pueden hacer las bases de datos SQL.

El método se describe aquí: enlace

Pero lo esencial es (parafraseando el enlace):

  1. Almacena todos sus puntos geocontenidos en la mejor resolución que desee (por lo general, el máximo es un entero de 64 bits si es accesible, o en el caso de javascript, 52 bits) en un conjunto ordenado (es decir, zset en redis). La mayoría de las bibliotecas de geohash en estos días tienen funciones integradas de geohash, y tendrás que usarlas en lugar de los geohashes base32 más comunes.
  2. Según el radio en el que desea buscar, debe encontrar una profundidad / resolución de bits que coincida con su área de búsqueda y debe ser menor o igual a la profundidad de bits de Geohash almacenada. El sitio vinculado tiene una tabla que correlaciona la profundidad de bits de un geohash con el área del cuadro delimitador en metros.
  3. Luego recargas tu coordenada original en esta resolución más baja.
  4. En esa resolución más baja también encuentre las 8 áreas de geohash vecinas (n, ne, e, se, s, sw, w, nw). La razón por la cual tiene que hacer el método vecino, es porque dos coordenadas casi una al lado de la otra podrían tener geohashes completamente diferentes, por lo que debe hacer un promedio del área cubierta por la búsqueda.
  5. Una vez que obtenga todos los geohashes vecinos en esta resolución inferior, agregue a la lista el geohash de sus coordenadas del paso 3.
  6. Luego necesitas crear un rango de valores de geohash para buscar dentro de estos 9 áreas. Los valores del paso 5 son su límite de rango inferior, y si agrega 1 a cada uno de ellos, obtendrá su límite de rango superior. Por lo tanto, debe tener una matriz de 9 rangos, cada uno con un límite inferior y un límite superior de geohash (18 geohashes en total). Estos geohashes aún se encuentran en esa resolución más baja del paso 2.
  7. Luego conviertes los 18 de estos gehashes a cualquier profundidad de bit / resolución en la que hayas almacenado todos tus geohashes en tu base de datos. Generalmente, lo haces cambiando a la profundidad de bit deseada.
  8. Ahora puede hacer una consulta de rango para los puntos dentro de estos 9 rangos y obtendrá todos los puntos aproximadamente dentro de la distancia de su punto original. No habrá superposición, por lo que no es necesario hacer intersecciones, solo consultas de rango puro, muy rápido. (es decir, en redis: ZRANGEBYSCORE zsetname lowerLimit upperLimit, en los 9 rangos producidos en este paso)

Puede optimizar más (de manera rápida) esto:

  1. Tomando esos 9 rangos desde el paso 6 y encontrando hacia dónde se dirigen entre sí. Por lo general, puede reducir 9 rangos separados en aproximadamente 4 o 5, dependiendo de dónde se encuentre su coordenada. Esto puede reducir su tiempo de consulta a la mitad.
  2. Una vez que tenga sus rangos finales, debe mantenerlos para reutilizarlos. El cálculo de estos rangos puede tomar la mayor parte del tiempo de procesamiento, por lo que si su coordenada original no cambia mucho pero necesita volver a realizar la misma consulta de distancia, debe tenerla lista en lugar de calcularla cada vez.
  3. Si está utilizando redis, intente combinar las consultas en un MULTI / EXEC para que las canalice para un mejor rendimiento.
  4. La MEJOR parte: puede distribuir los pasos 2 a 7 en los clientes en lugar de tener ese cálculo hecho en un solo lugar. Esto reduce en gran medida la carga de la CPU en situaciones en las que se recibirían millones de solicitudes.

Puede mejorar aún más la precisión mediante el uso de una función de tipo círculo distancia / haversina en los resultados obtenidos si le importa mucho la precisión.

Aquí hay una técnica similar que usa geohashes base32 ordinarios y una consulta SQL en lugar de redis: enlace

No quiero conectar mi propia cosa, pero he escrito un módulo para nodejs & redis que hace que esto sea realmente fácil de implementar. Mire el código si desea: enlace

    
respondido por el Arjun Mehta 08.04.2014 - 12:10
9

La pregunta se puede leer de varias maneras. Interpreto que significa que tiene una gran cantidad de puntos y que tiene la intención de sondearlos repetidamente con puntos arbitrarios, dados como pares de coordenadas, y desea obtener los n puntos más cercanos a la sonda, con n de antemano. (En principio, si n variará, puede configurar una estructura de datos para cada n posible y seleccionarla en O (1) tiempo con cada sonda: esto puede llevar un tiempo de configuración muy largo y requiere una gran cantidad de RAM, pero se nos dice que ignoremos tales preocupaciones.)

Cree el orden-n diagrama de Voronoi de Todos los puntos. Esto divide el plano en regiones conectadas, cada una de las cuales tiene los mismos n vecinos. Esto reduce la situación al problema de punto en polígono, que tiene muchas soluciones eficientes.

Usando una estructura de datos vectoriales para el diagrama de Voronoi, las búsquedas de punto en polígono tomarán tiempo O (log (n)). Por motivos prácticos, puede hacer este O (1) con un coeficiente implícito extremadamente pequeño simplemente creando una versión rasterizada del diagrama. Los valores de las celdas en el ráster son (i) un puntero a una lista de los n puntos más cercanos o (ii) una indicación de que esta celda se extiende a lo largo de dos o más regiones en el diagrama. La prueba para un punto arbitrario en (x, y) se convierte en:

Fetch the cell value for (x,y).
If the value is a list of points, return it.
Else apply a vector point-in-polygon algorithm to (x,y).

Para lograr el rendimiento de O (1), la malla ráster debe ser lo suficientemente fina para que caigan relativamente pocos puntos de prueba en las celdas que se encuentran a lo largo de varias regiones Voronoi. Esto siempre se puede lograr, con un gasto potencialmente grande en el almacenamiento de las cuadrículas.

    
respondido por el whuber 31.12.2011 - 19:22
3

Uso geohashes para exactamente esto. La razón por la que lo soy es porque necesitaba implementar búsquedas de proximidad utilizando un sistema de información de estilo piramidal ... donde los geohashes con una precisión de nivel 8 eran la "base" y formaban nuevos totales para los geohashes de la 7ª precisión ... y así sucesivamente . Estos totales eran área, tipos de cobertura del suelo, etc. Era una forma muy elegante de hacer algunas cosas muy elegantes.

Por lo tanto, los geohashes de 8vo nivel contendrían información como:

tipo: hierba acres: 1.23

y 7, 6, etc., contendrían información como:

tipos de hierba: 123 acres: 6502

Esto siempre se construyó a partir de la precisión más baja. Esto me permitió hacer todo tipo de estadísticas divertidas muy rápidamente. También pude asignar una referencia de geometría a cada referencia de geohash usando GeoJSON.

Pude escribir varias funciones para encontrar los geohashes más grandes que conforman mi viewport actual y luego usarlos para encontrar geohashes de la segunda precisión más grande dentro del viewport. Esto podría extenderse fácilmente a las consultas de rango indexado en las que consultaría un mínimo de '86ssaaaa' y un máximo de '86sszzzz' para cualquier precisión que yo quisiera.

Estoy haciendo esto usando MongoDB.

    
respondido por el whardier 15.01.2013 - 22:39
3

Actualización para 2018, y algunas fundaciones matemáticas o procedencia histórica de Geohash:

  • la inspiración para Geohash fue el interlave simple de dígitos binarios , quizás un Optimización de algoritmos ingenuos que intercalaban dígitos decimales, como el C-squares .

  • el entrelazado binario dio como resultado una estrategia de índice Z-order-curve naturalmente, inventor de Geohash < strong> not comenzó a "buscar la mejor curva fractal" ... Pero curiosamente, esta optimización de diseño, una mejor curva fractal, es posible (!).

Usar la biblioteca de geometría S2

El enfoque de geometría S2 es mejor que Geohash porque usa la topología esférica del globo (un cubo), usa el opcional proyección (por lo que todas las celdas tienen casi la misma forma y área cercana), y debido a la indexación con curva de Hilbert es mejor que curva de orden Z :

  

... podemos hacerlo mejor ... La discontinuidad a medida que avanzamos del cuadrante superior derecho al cuadrante inferior izquierdo nos obliga a dividir algunos rangos que de otro modo podríamos hacer contiguos. (...) podemos eliminar completamente cualquier discontinuidad (...)
blog.notdot.net/2009 sobre indexación espacial con Quadtrees y Hilbert Curves

Ahora es una biblioteca gratuita y eficiente, consulte enlace

PS: también hay (buenas) versiones simplificadas no oficiales como s2-geometry de NodeJS, y muchas "parques infantiles", complementos y demostraciones, como s2.sidewalklabs.com .

    
respondido por el Peter Krauss 18.12.2018 - 20:55
2

Recomendaría utilizar la consulta GEORADIUS en redis.

Empuje los datos fragmentados por el nivel de geohash más adecuado usando la llamada GEOADD.

También, eche un vistazo a esto - > ProximityHash .

ProximityHash genera un conjunto de geohashes que cubren un área circular, dadas las coordenadas del centro y el radio. También tiene una opción adicional para usar GeoRaptor que crea la mejor combinación de geohashes en varios niveles para representar el círculo, comenzando desde el nivel más alto e iterando hasta que se elabora la combinación óptima. La precisión de los resultados sigue siendo la misma que la del nivel de inicio de geohash, pero el tamaño de los datos se reduce considerablemente, lo que mejora la velocidad y el rendimiento.

    
respondido por el Ashwin Nair 15.02.2017 - 07:24

Lea otras preguntas en las etiquetas