Utiliser geohash pour les recherches de proximité?

Je cherche à optimiser le temps de recherche géo de proximité de points.

Mon entrée est lat, lng point et je recherche un ensemble de lieux précalculés vers n points les plus proches.

Peu m'importe combien de temps / d'espace la construction de l'index des emplacements précalculé prendra, mais je m'inquiète que les requêtes soient super rapides.

Je pense à utiliser geohash comme clé de recherche, où je vérifierais d'abord si j'obtiens des résultats pour X caractères de la clé, puis continue à réduire les caractères à partir de la fin de la clé jusqu'à ce que je commence à voir les résultats.

Pour ma compréhension (très limitée pour l'instant) des techniques de géo-index, cette approche devrait être en mesure de produire les résultats les plus rapides (en termes de temps de requête) par rapport à toutes les autres implémentations connues (telles que R Tree and co.)

Vous le pouvez absolument. Et cela peut être assez rapide. (Les bits de calcul intensifs peuvent également être distribués)

Il y a plusieurs façons, mais une façon avec laquelle j'ai travaillé est d'utiliser une liste ordonnée de géohashs basés sur des nombres entiers et de trouver toutes les plages de geohash les plus proches pour une résolution de geohash spécifique (la résolution se rapproche de vos distancecritères), puis interroger ces gammes de geohash pour obtenir une liste des points à proximité. J'utilise redis et nodejs (ie. Javascript) pour cela. Redis est super rapide et peut récupérer les plages ordonnées très rapidement, mais il ne peut pas faire beaucoup de choses de manipulation de requête d'indexation que les bases de données SQL peuvent faire.

La méthode est décrite ici: https://github.com/yinqiwen/ardb/wiki/Spatial-Index

Mais l'essentiel est (pour paraphraser le lien):

1. Vous stockez tous vos points géo-hachurés dans la meilleure résolution que vous souhaitez (max 64 bits généralement si c'est accessible, ou dans le cas de javascript, 52 bits) dans un ensemble ordonné (c'est-à-dire zset in redis). La plupart des bibliothèques geohash de nos jours ont des fonctions entières geohash intégrées, et vous devrez les utiliser à la place des géohashes base32 les plus courants.
2. En fonction du rayon dans lequel vous souhaitez rechercher, vous devez ensuite trouver une profondeur / résolution en bits qui correspondra à votre zone de recherche et celle-ci doit être inférieure ou égale à la profondeur de bits de votre geohash stockée. Le site lié possède un tableau qui met en corrélation la profondeur de bits d'un géohach avec sa zone de délimitation en mètres.
3. Ensuite, vous remaniez vos coordonnées d'origine à cette résolution inférieure.
4. À cette résolution inférieure, trouvez également les 8 zones de géohash voisines (n, ne, e, se, s, sw, w, nw). La raison pour laquelle vous devez faire la méthode du voisin est que deux coordonnées presque côte à côte pourraient avoir des géohashes complètement différents, vous devez donc faire une moyenne de la zone couverte par la recherche.
5. Une fois que vous avez obtenu tous les géohash voisins à cette résolution inférieure, ajoutez à la liste le géohash de vos coordonnées à partir de l'étape 3.
6. Ensuite, vous devez créer une plage de valeurs de geohash pour rechercher à l'intérieur de ces 9 zones. Les valeurs de l'étape 5 sont votre limite de plage inférieure, et si vous ajoutez 1 à chacune d'elles, vous obtiendrez votre limite de plage supérieure. Vous devriez donc avoir un tableau de 9 plages, chacune avec une limite inférieure et une limite de géohash supérieure (18 géohashes au total). Ces géohashes sont toujours dans cette résolution inférieure à l'étape 2.
7. Ensuite, vous convertissez tous les 18 de ces geohashes à la profondeur / résolution de bits dans laquelle vous avez stocké tous vos geohashes dans votre base de données. En général, vous le faites en le décalant en bits à la profondeur de bits souhaitée.
8. Vous pouvez maintenant faire une requête de plage pour les points dans ces 9 plages et vous obtiendrez tous les points à peu près à la distance de votre point d'origine. Il n'y aura pas de chevauchement, vous n'avez donc pas besoin de faire d'intersections, juste des requêtes de plage pure, très rapidement. (c.-à-d. en redis: ZRANGEBYSCORE zsetname lowerLimit upperLimit, sur les 9 plages produites dans cette étape)

Vous pouvez encore optimiser (en termes de vitesse) ceci en:

1. Prendre ces 9 va de l'étape 6 et trouver où ils mènent les uns aux autres. Habituellement, vous pouvez réduire 9 plages distinctes en environ 4 ou 5 selon l'endroit où se trouvent vos coordonnées. Cela peut réduire de moitié le temps de requête.
2. Une fois que vous avez vos gammes finales, vous devez les conserver pour les réutiliser. Le calcul de ces plages peut prendre la plupart du temps de traitement, donc si votre coordonnée d'origine ne change pas beaucoup mais que vous devez refaire la même requête de distance, vous devez la garder prête au lieu de la calculer à chaque fois.
3. Si vous utilisez redis, essayez de combiner les requêtes dans un MULTI / EXEC afin qu'il les redirige vers des performances un peu meilleures.
4. La MEILLEURE partie: vous pouvez distribuer les étapes 2 à 7 sur les clients au lieu de faire ce calcul en un seul endroit. Cela réduit considérablement la charge du processeur dans des situations où des millions de demandes devraient arriver.

Vous pouvez encore améliorer la précision en utilisant une fonction de type cercle de distance / haversine sur les résultats renvoyés si vous vous souciez beaucoup de la précision.

Voici une technique similaire utilisant des geohashes base32 ordinaires et une requête SQL au lieu de redis: https://github.com/davetroy/geohash-js

Je ne veux pas brancher mon propre truc, mais j'ai écrit un module pour nodejs & redis qui rend cela vraiment facile à implémenter. Jetez un œil au code si vous le souhaitez: https://github.com/arjunmehta/node-georedis

La question peut être lue de plusieurs manières. Je l'interprète comme signifiant que vous avez un grand nombre de points et que vous avez l'intention de les sonder à plusieurs reprises avec des points arbitraires, donnés sous forme de paires de coordonnées, et que vous souhaitez obtenir les n points les plus proches de la sonde, avec n fixé au préalable. (En principe, si n varie, vous pouvez configurer une structure de données pour chaque n possible et la sélectionner en temps O (1) avec chaque sonde: cela pourrait prendre un temps de configuration très long et nécessiter beaucoup de RAM, mais nous sont invités à ignorer ces préoccupations.)

Construisez le diagramme Voronoi order-n de tous les points. Cela divise l'avion en régions connectées, chacune ayant les mêmes n voisins. Cela réduit la situation au problème du point dans le polygone, qui a de nombreuses solutions efficaces.

En utilisant une structure de données vectorielles pour le diagramme de Voronoi, les recherches ponctuelles dans un polygone prendront O (log (n)). Pour des raisons pratiques, vous pouvez créer cet O (1) avec un coefficient implicite extrêmement faible simplement en créant une version raster du diagramme. Les valeurs des cellules du raster sont soit (i) un pointeur vers une liste des n points les plus proches, soit (ii) une indication que cette cellule chevauche deux régions ou plus dans le diagramme. Le test d'un point arbitraire en (x, y) devient:

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).

Pour obtenir des performances O (1), le maillage raster doit être suffisamment fin pour que relativement peu de points de sonde tombent dans des cellules qui chevauchent plusieurs régions de Voronoi. Cela peut toujours être accompli, avec des dépenses potentiellement importantes en stockage pour les grilles.

J'utilise des geohashes exactement pour cela. La raison pour laquelle je suis parce que je devais implémenter des recherches de proximité en utilisant un système d'information de style pyramidal .. où les géohashes avec une précision de 8ème niveau étaient la 'base' et formaient de nouveaux totaux pour les geohashes de la 7ème précision .. et ainsi de suite et ainsi de suite . Ces totaux étaient des superficies, des types de couvre-sol, etc. C'était une façon très sophistiquée de faire des trucs très sophistiqués.

Ainsi, les géohashes de 8e niveau contiendraient des informations telles que:

type: gazon acres: 1,23

et les 7e, 6e, etc. contiendraient des informations comme:

grass_types: 123 acres: 6502

Cela a toujours été construit à partir de la plus faible précision. Cela m'a permis de faire toutes sortes de statistiques amusantes très rapidement. J'ai également pu attribuer une référence géométrique à chaque référence geohash à l'aide de GeoJSON.

J'ai pu écrire plusieurs fonctions pour trouver les plus grands géohashs qui composent ma fenêtre actuelle, puis les utiliser pour trouver des géohashes de la deuxième plus grande précision dans la fenêtre. Cela pourrait facilement être étendu aux requêtes de plage indexée où je demanderais un minimum de '86ssaaaa' et un maximum de '86sszzzz' pour la précision que je voulais.

Je fais cela en utilisant MongoDB.

Mise à jour pour 2018 et certaines fondations mathématiques ou provenance historique de Geohash:

• l'inspiration pour geohash était le simple , interlave de chiffres binaires , peut - être une optimisation des algorithmes naïfs intercalées chiffres décimaux, comme les des carrés C- .

• l'entrelacement binaire a abouti à une stratégie d'indice de courbe d'ordre Z naturellement, l'inventeur de Geohash n'a pas commencé "à chercher la meilleure courbe fractale" ... Mais curieusement, cette optimisation de conception, une meilleure courbe fractale, est possible (!).

Utiliser la bibliothèque de géométrie S2

L'approche de la géométrie S2 est meilleure que Geohash car elle utilise la topologie sphérique du globe (un cube), utilise une projection optionnelle (de sorte que toutes les cellules ont presque la même forme et la même zone), et parce que l'indexation avec la courbe de Hilbert est meilleure tham Z- courbe d'ordre :

... nous pouvons faire mieux ... La discontinuité lorsque nous passons du quadrant supérieur droit au coin inférieur gauche nous oblige à diviser certaines plages que nous pourrions autrement rendre contiguës. (...) nous pouvons éliminer complètement les discontinuités (...)
blog.notdot.net/2009 sur l'indexation spatiale avec Quadtrees et Hilbert Curves

Maintenant, c'est une bibliothèque gratuite et efficace, voir https://s2geometry.io

PS: il existe également de (bonnes) versions simplifiées non officielles comme NodeJSs2-geometry , et de nombreux "terrains de jeux", compléments et démos, comme s2.sidewalklabs.com .

Je recommanderais d'utiliser la requête GEORADIUS dans redis.

Poussez les données partagées par le niveau de geohash le mieux adapté à l'aide de l'appel GEOADD.

Jetez également un œil à ceci -> ProximityHash .

ProximityHash génère un ensemble de géohashes qui couvrent une zone circulaire, étant donné les coordonnées du centre et le rayon. Il a également une option supplémentaire pour utiliser GeoRaptor qui crée la meilleure combinaison de géohashes à différents niveaux pour représenter le cercle, en commençant par le plus haut niveau et en itérant jusqu'à ce que le mélange optimal soit brassé. La précision des résultats reste la même que celle du niveau de geohash de départ, mais la taille des données diminue considérablement, améliorant ainsi la vitesse et les performances.