Recherche de proximité

Question

Comment une application effectue-t-elle une recherche de proximité? Par exemple, un utilisateur entre un code postal, puis l'application répertorie toutes les entreprises situées dans un rayon de 20 km par ordre de proximité.

Je veux construire quelque chose comme ça en PHP et MySQL. Cette approche est-elle correcte?

1. Obtenir les adresses des lieux qui m'intéressent et les stocker dans ma base de données
2. géocodez toutes les adresses avec le service de géocodage de Google
3. Écrivez une requête dans la base de données contenant la formule Haversine pour effectuer la recherche et le classement par proximité

Est-ce que ça va? À l'étape 3, je vais calculer la proximité pour chaque requête. Est-il préférable d’avoir un tableau PROXIMITY qui répertorie la distance entre chaque entreprise et quelques sites de référence?

Answer 1

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

Définissez une grille de cases d'environ 20 miles sur un côté. Enregistrez le numéro de la corbeille avec l'enregistrement de chaque magasin. Au moment de la recherche, calculez le nombre de cases qui coupent un rayon de 20 milles de votre point de recherche. Récupérez ensuite tous les magasins de ces bacs et procédez comme avant.

Answer 2

Nous l'utilisons pour faire plusieurs milliers de points. Il est important, si vous effectuez cette opération en SQL, d’avoir un index sur les colonnes Latitude et Longitude. Nous avons essayé de le faire dans SQL 2008 avec des index spatiaux mais nous n’avons vraiment pas vu l’augmentation des performances escomptée. Cependant, si vous souhaitez calculer à une certaine distance d'un ZIP, vous devez vous demander si vous allez utiliser le centroïde ZIP ou une représentation polygonale du code ZIP.

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 le calculons à l’avance pour certaines applications où nous connaissons les points à l’avance et où 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

Answer 3

Nous le faisons pour environ 1200 emplacements. Je voudrais juste utiliser la formule Haversine à la volée bien que selon votre application, il soit peut-être préférable de la stocker en PHP plutôt qu'en SQL. (Notre implémentation est en .net, donc votre kilométrage peut varier).

Notre principal inconvénient de la manière dont nous l'avons implémenté est que chaque calcul (jusqu'à récemment) devait être calculé sur le niveau de données qui était terriblement lent (quand je dis lent, je veux dire vraiment non instantané, il a fallu seconde ou à peu près), mais cela était dû au fait qu’il devait calculer la distance pour les 1 200 emplacements en fonction du code postal fourni.

En fonction de l’itinéraire que vous choisissez, il est possible d’accélérer les calculs de distance en calculant la longitude et la latitude et en supprimant ceux qui se trouvent en dehors d’une plage prédéfinie (par exemple, si vous recherchez toutes les adresses situées à moins de 30 km). il existe une plage de longitude que vous pouvez calculer pour laquelle toutes les adresses doivent se situer dans un rayon de 20 miles.) Cela peut accélérer la recherche si besoin est.

Nous avons en fait envisagé de stocker toutes les combinaisons possibles dans notre base de données. En réalité, il semble que cela puisse être un grand magasin de données, mais ce n’est vraiment pas dans la grande portée des choses. Avec les index, cela peut être assez rapide et vous n'avez pas à vous soucier de l'optimisation de l'algorithme, etc. Nous avons décidé de ne pas le faire, car nous avions l'équation en C # et cela nous permettait de mettre en cache les informations nécessaires pour effectuer tous les calculs de la niveau entreprise. L'un ou l'autre fonctionnera très bien, c'est juste une question de votre préférence.