¿Usa geohash para búsquedas de proximidad?

Estoy buscando optimizar el tiempo de búsqueda geográfica de proximidad de puntos.

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

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

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

A mi entender (muy escaso 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 demás implementaciones conocidas (como R Tree y compañía).

Absolutamente puedes. Y puede ser bastante rápido. (Los bits de cálculo intensivo TAMBIÉN se pueden distribuir)

Hay varias formas, pero una de las que he estado trabajando es mediante el uso de una lista ordenada de geohashes basados ​​en enteros, y encontrar todos los rangos de geohash vecinos más cercanos para una resolución específica de geohash (la resolución se aproxima a sus distancecriterios), y luego consultar esos rangos de geohash para obtener una lista de puntos cercanos. Utilizo redis y nodejs (es decir, javascript) para esto. Redis es súper rápido y puede recuperar rangos ordenados muy rápidamente, pero no puede hacer muchas de las cosas de manipulación de consultas de indexación que pueden hacer las bases de datos SQL.

El método se describe aquí: https://github.com/yinqiwen/ardb/wiki/Spatial-Index

Pero lo esencial es (parafraseando el enlace):

1. Usted almacena todos sus puntos geohashed en la mejor resolución que desee (generalmente un número 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 enteras de geohash integradas, y deberá usarlas en lugar de las 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 esta 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 su área de cuadro delimitador en metros.
3. Luego repite su coordenada original con 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 que debe 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 todas las geohashes vecinas en esta resolución más baja, agregue a la lista la geohash de su coordenada del paso 3.
6. Luego, debe crear un rango de valores de geohash para buscar dentro de los cuales cubra estas 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). Estas geohashes todavía están en esa resolución más baja del paso 2.
7. Luego convierte los 18 de estas geohashes a cualquier profundidad / resolución de bits en la que haya almacenado todas sus geohashes en su base de datos. Generalmente lo hace desplazándolas a la profundidad de bits 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 necesita hacer ninguna intersección, 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 aún más (en cuanto a velocidad):

1. Tomando esos 9 rangos desde el paso 6 y encontrando dónde conducen entre sí. Por lo general, puede reducir 9 rangos separados en aproximadamente 4 o 5 dependiendo de dónde esté su coordenada. Esto puede reducir el tiempo de consulta a la mitad.
2. Una vez que tenga sus rangos finales, debe mantenerlos para su reutilización. El cálculo de estos rangos puede llevar la mayor parte del tiempo de procesamiento, por lo que si su coordenada original no cambia mucho pero necesita realizar la misma consulta de distancia nuevamente, 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 rendimiento un poco mejor.
4. La MEJOR parte: puede distribuir los pasos 2 a 7 en los clientes en lugar de hacer que el cálculo se realice en un solo lugar. Esto reduce en gran medida la carga de la CPU en situaciones en las que llegarían millones de solicitudes.

Puede mejorar aún más la precisión utilizando una función de tipo círculo distancia / haversine en los resultados devueltos si le importa mucho la precisión.

Aquí hay una técnica similar usando geohashes base32 ordinarios y una consulta SQL en lugar de redis: https://github.com/davetroy/geohash-js

No pretendo enchufar lo mío, pero he escrito un módulo para nodejs y redis que hace que sea realmente fácil de implementar. Eche un vistazo al código si desea: https://github.com/arjunmehta/node-georedis

La pregunta podría leerse 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 fijado de antemano. (En principio, si n variará, podría configurar una estructura de datos para cada n posible y seleccionarla en tiempo O (1) con cada sonda: esto podría llevar un tiempo de configuración muy largo y requerir una gran cantidad de RAM, pero se les dice que ignoren tales preocupaciones).

Construye el diagrama order-n 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 el polígono, que tiene muchas soluciones eficientes.

Usando una estructura de datos vectoriales para el diagrama de Voronoi, las búsquedas de punto en el polígono tomarán tiempo O (log (n)). Para fines prácticos, puede hacer este O (1) con un coeficiente implícito extremadamente pequeño simplemente creando una versión ráster 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 entre 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 de trama tiene que ser lo suficientemente fina como para que relativamente pocos puntos de sonda caigan en celdas que se extienden a horcajadas sobre múltiples regiones de Voronoi. Esto siempre se puede lograr, con un gasto potencialmente grande en almacenamiento para las redes.

Yo uso geohashes para exactamente esto. La razón por la que estoy es porque necesitaba implementar búsquedas de proximidad usando un sistema de información de estilo piramidal ... donde las geohashes con una precisión de 8 ° nivel eran la 'base' y formaban nuevos totales para 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, las geohashes del octavo nivel contendrían información como:

tipo: acres de hierba: 1.23

y séptimo, sexto ... etc. contendrían información como:

tipos de césped: 123 acres: 6502

Esto siempre se construyó con 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 las geohashes más grandes que conforman mi ventana gráfica actual y luego usarlas para encontrar geohashes de la segunda precisión más grande dentro de la ventana gráfica. Esto podría extenderse fácilmente a las consultas de rango indexado donde consultaría un mínimo de '86ssaaaa' y un máximo de '86sszzzz' para cualquier precisión que quisiera.

Estoy haciendo esto usando MongoDB.

Actualización para 2018 y algunos fundamentos matemáticos o procedencia histórica de Geohash:

• la inspiración para geohash fue la sencilla interlave de dígitos binarios , tal vez una optimización de algoritmos ingenuos que intercalan dígitos decimales, al igual que la de C-cuadrados .

• el entrelazado binario resultó en una estrategia de índice de curva de orden Z naturalmente, el inventor de Geohash no 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 proyección opcional (para que todas las celdas tengan casi la misma forma y área cercana), y porque la indexación con la curva de Hilbert es mejor que Z- curva de orden :

... podemos hacerlo mejor ... La discontinuidad a medida que avanzamos desde el cuadrante superior derecho al inferior izquierdo hace que tengamos que dividir algunos rangos que de otro modo podríamos hacer contiguos. (...) podemos eliminar por completo cualquier discontinuidad (...)
blog.notdot.net/2009 sobre indexación espacial con curvas Quadtrees y Hilbert

Ahora es una biblioteca gratuita y eficiente, consulte https://s2geometry.io

PD: también hay (simplificadas) versiones simplificadas no oficiales como NodeJSs2-geometry y muchos "parques infantiles", complementos y demostraciones, como s2.sidewalklabs.com .

Recomendaría usar la consulta GEORADIUS en redis.

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

Además, 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 prepare la mezcla óptima. La precisión del resultado sigue siendo la misma que la del nivel inicial de geohash, pero el tamaño de los datos se reduce considerablemente, mejorando así la velocidad y el rendimiento.