Recherche de proximité

Question

Comment une application effectue-t-elle une recherche de proximité? Par exemple, un utilisateur tape un code postal, puis l'application répertorie toutes les entreprises dans les 20 miles classés par proximité. Je veux construire quelque chose comme ça en PHP et MySQL. Cette approche est-elle correcte?

1. obtenir les adresses pour les endroits qui me intéressent et stocker dans ma base de données
2. Géocoder toutes les adresses avec le service de géocodage de Google
3. Ecrire une requête de base de données qui comprend la formule Haversine pour faire la recherche de proximité et commande

Est-ce correct? À l'étape 3, je vais calculer la proximité pour chaque requête. Est-il préférable d'avoir une table PROXIMITY qui répertorie la distance entre chaque entreprise et quelques endroits de référence?

Answer 1

S'il y a suffisamment d'enregistrements pour que la vitesse compte, voici un moyen de les indexer à l'avance.

Définir une grille de bacs d'environ 20 milles de côté. Stockez le numéro de casier avec l'enregistrement de chaque magasin. Au moment de la recherche, calculez le nombre de tous les intervalles qui se croisent dans un rayon de 20 milles de votre point de recherche. Récupérez ensuite tous les magasins dans l'un de ces emplacements et procédez comme précédemment.

Answer 2

Nous faisons cela pour environ 1200 emplacements. Je voudrais juste utiliser la formule de Haversine à la volée bien que selon votre application, il pourrait être préférable de le stocker en PHP au lieu de SQL. (Notre implémentation est en .net donc votre kilométrage peut varier). Vraiment notre plus grand inconvénient avec la façon dont nous l'avons implémenté, c'est que chaque calcul (jusqu'à récemment) devait être calculé sur le niveau de données qui était douloureusement lent (quand je dis lent, je veux dire vraiment non-instantané il a fallu une seconde ou deux), mais cela était dû au fait qu'il devait calculer la distance pour tous les 1200 emplacements en fonction du code postal fourni. Selon l'itinéraire que vous choisissez, il existe des moyens d'accélérer les calculs de distance numérique, en regardant la longitude et la latitude et en supprimant celles en dehors d'une plage prédéfinie (par exemple, si vous regardez toutes les adresses dans un rayon de 20 km). miles il y a une gamme de longitude que vous pouvez calculer et que toutes les adresses doivent tomber à 20 miles de distance.) Cela peut accélérer votre requête si nécessaire.

En fait, nous avons cherché à stocker toutes les combinaisons possibles dans notre base de données. En réalité, il semble que ce pourrait être un grand magasin de données, mais ce n'est vraiment pas dans le grand champ des choses. Avec les index il peut être assez rapide, et vous n'avez pas à vous inquiéter de l'optimisation de l'algorithme, etc. Nous avons décidé contre, car nous avions l'équation en C#, et cela nous a permis de cacher les informations nécessaires pour faire tous les calculs. niveau d'entreprise. Soit fonctionnera très bien, c'est juste une question de ce que vous préférez.

Answer 3

Nous utilisons ceci pour faire plusieurs milliers de points. Il est important, si vous effectuez cela en SQL, d'avoir un index sur la colonne Latitude et Longitude. Nous avons essayé de le faire dans SQL 2008 avec des index spatiaux mais nous n'avons pas vraiment vu l'augmentation de performance que nous attendions. Bien que si vous voulez calculer à une certaine distance d'un ZIP vous devez penser si vous allez utiliser le centroïde ZIP ou une représentation polygonale du code postal.

Haversine forumla est un bon point de départ.

Nous n'avons pas eu de problèmes de performances pour calculer la distance à la volée, nous la calculons à l'avance pour certaines applications où nous connaissons les points à l'avance et il y aura des millions d'enregistrements.

SELECT 
     [DistanceRadius]= 
     69.09 * 
     DEGREES(
      ACOS(
      SIN(RADIANS(latitude))*SIN(RADIANS(@ziplat)) 
      + 
      COS(RADIANS(latitude))*COS(RADIANS(@ziplat)) 
      * 
      COS(RADIANS(longitude - (@ziplon))) 
     ) 
     ) 
     ,* 
     FROM 
      table 

    ) sub 
WHERE 
    sub.DistanceRadius < @radius