Calculer la distance entre les Codes postaux... ET les utilisateurs.

Je serais tout simplement il suffit de créer un zip_code_distances table et de pré-calculer les distances entre tous les 42K zipcodes aux etats-unis qui sont dans un de 20 à 25 km autour de chaque d'autres.

create table zip_code_distances
(
from_zip_code mediumint not null,
to_zip_code mediumint not null,
distance decimal(6,2) default 0.0,
primary key (from_zip_code, to_zip_code),
key (to_zip_code)
)
engine=innodb;

Seulement, y compris zipcodes dans un de 20 à 25 milles de rayon de réduire le nombre de lignes dont vous avez besoin pour stocker dans le tableau des distances de maximum de 1,7 milliard de dollars (42K ^ 2) - 42K à une beaucoup plus gérable 4 millions.

J'ai téléchargé un code postal fichier de données à partir du web qui contient les latitudes et longitudes de tous les officiels NOUS zipcodes au format csv:

"00601","Adjuntas","Adjuntas","Puerto Rico","PR","787","Atlantic", 18.166, -66.7236
"00602","Aguada","Aguada","Puerto Rico","PR","787","Atlantic", 18.383, -67.1866
...
"91210","Glendale","Los Angeles","California","CA","818","Pacific", 34.1419, -118.261
"91214","La Crescenta","Los Angeles","California","CA","818","Pacific", 34.2325, -118.246
"91221","Glendale","Los Angeles","California","CA","818","Pacific", 34.1653, -118.289
...

J'ai écrit un rapide et sale programme C# pour lire le fichier et de calculer les distances entre chaque code postal, mais seulement de la sortie zipcodes qui relèvent de 25 milles de rayon:

sw = new StreamWriter(path);

foreach (ZipCode fromZip in zips){

    foreach (ZipCode toZip in zips)
    {
        if (toZip.ZipArea == fromZip.ZipArea) continue;

        double dist = ZipCode.GetDistance(fromZip, toZip);

        if (dist > 25) continue;

        string s = string.Format("{0}|{1}|{2}", fromZip.ZipArea, toZip.ZipArea, dist);
        sw.WriteLine(s);
    }
}

La résultante de sortie de fichier se présente comme suit:

from_zip_code|to_zip_code|distance
...
00601|00606|16.7042215574185
00601|00611|9.70353520976393
00601|00612|21.0815707704904
00601|00613|21.1780461311929
00601|00614|20.101431539283
...
91210|90001|11.6815708119899
91210|90002|13.3915723402714
91210|90003|12.371251171873
91210|90004|5.26634939906721
91210|90005|6.56649623829871
...

Je voudrais ensuite il suffit de charger ce que les données de distance dans mon zip_code_distances table à l'aide de load data infile et ensuite l'utiliser pour limiter l'espace de recherche de ma demande.

Par exemple, si vous avez un utilisateur dont le code postal est 91210 et ils veulent trouver des gens qui sont dans un rayon de 10 km autour d'eux, puis vous pouvez faire ce qui suit:

select 
 p.*
from
 people p
inner join
(
 select 
  to_zip_code 
 from 
  zip_code_distances 
 where 
  from_zip_code = 91210 and distance <= 10
) search
on p.zip_code = search.to_zip_code
where
 p.gender = 'F'....

Espère que cette aide

EDIT: étendue rayon de 100 miles qui a augmenté le nombre de code postal distances à 32,5 millions de lignes.

rapide contrôle de performance pour code postal 91210 exécution de 0,009 secondes.

select count(*) from zip_code_distances
count(*)
========
32589820

select 
 to_zip_code 
from 
 zip_code_distances 
where 
 from_zip_code = 91210 and distance <= 10;

0:00:00.009: Query OK

Vous pouvez diviser votre espace en régions d'une taille à peu près égale, par exemple, se rapproche de la terre comme un buckyball ou de l'icosaèdre. Les régions peuvent même se chevaucher un peu, si c'est plus facile (par exemple, faire de la circulaire). Enregistrer les région(s) chaque code POSTAL est dans. Ensuite, vous pouvez précalculer la distance maximale possible entre chaque région de la paire, qui a le même O(n^2) problème que le calcul de toutes le code POSTAL de paires, mais pour les plus petites n.

Maintenant, pour chaque code POSTAL, vous pouvez obtenir une liste des régions qui sont certainement au sein de votre gamme donnée, et une liste de régions qui traversent la frontière. Pour les premiers, il suffit de prendre tous les codes postaux. Pour ce dernier, de forage vers le bas dans chaque région de la frontière et de calculer à l'encontre de certains codes postaux.

C'est certainement plus complexe sur le plan mathématique, et en particulier le nombre de régions devrait être choisi pour un bon équilibre entre la taille de la table contre le temps passé à calculer à la volée, mais il réduit la taille de la table précalculée par une bonne marge.

Pas chaque paire possible de zip codes vont être utilisés. Je voudrais construire zipdistance comme un "cache" de la table. Pour chaque demande de calculer la distance pour cette paire et de les enregistrer dans la mémoire cache. Lorsqu'une demande pour une distance paire vient, de regarder d'abord dans le cache, puis calculer si il n'est pas disponible.

Je ne connais pas les subtilités de calculs de distance, donc je voudrais aussi vérifier si le calcul à la volée est moins cher que de rechercher (en tenant également compte de la façon dont vous avez souvent à calculer).

J'ai le problème fonctionne très bien, et à peu près tout le monde la réponse de l'ai utilisé. Je pensais à ce sujet dans les termes de l'ancienne solution au lieu de "recommencer." Babtek obtient le feu vert pour dire dans dans les termes les plus simples.

Je vais passer le code, parce que je vais vous donner les références pour en déduire le besoin de formules, et il y a trop à proprement poster ici.

1) d'Envisager d'Un Point sur une sphère, représentée par la latitude et la longitude. Comprendre Nord, le Sud, l'Est et à l'Ouest les bords de la boîte 2X kilomètres avec Un Point au centre.

2) Sélectionnez tous les points à l'intérieur de la boîte à partir du code Postal de la table. Cela inclut une simple clause where avec les deux Entre les déclarations de limiter par la Lat et Long.

3) Utiliser le haversine formule pour déterminer la partie sphérique de la distance entre Un Point et chaque point de B renvoyé à l'étape 2.

4) Jeter tous les points B où la distance A -> B > X.

5) Sélectionnez où les utilisateurs code Postal est dans le reste de l'ensemble de points B.

C'est assez rapide pour > 100 miles. La plus longue suite a ~ de 0,014 secondes pour calculer le match, et trivial pour exécuter l'instruction select.

Aussi, comme une note de côté, il était nécessaire de mettre en œuvre les mathématiques dans un couple de fonctions et de les appeler dans SQL. Une fois que j'ai passé une certaine distance, le numéro correspondant de ZipCodes était trop gros pour passer à SQL et l'utilisation comme DANS l'énoncé, j'ai donc dû utiliser une table temporaire et rejoindre la résultante ZipCodes à l'Utilisateur sur le code Postal de la colonne.

Je soupçonne que l'utilisation d'un ZipDistance table ne sera pas fournir un rendement à long terme de gain. Le nombre de lignes devient vraiment grand. Si vous de calculer la distance de chaque zip à tous les autres zip code (éventuellement), alors la résultante du nombre de lignes de 40 000 codes postaux serait ~ 1.6 B. Whoah!

En alternance, je suis intéressé par l'utilisation de SQL intégré de type géographie à voir si cela va rendre cela plus facile, mais la bonne vieille int/float types servi amende pour cet échantillon.

Donc... la liste définitive des ressources en ligne que j'ai utilisé, pour votre référence:

1) La Différence maximale, la Latitude et la Longitude.

2) La Formule Haversine.

3) Longue mais complète la discussion de l'ensemble du processus, que j'ai trouvé de Googler trucs dans vos réponses.