database - Calcule la distancia entre los códigos postales... Y los usuarios.
gis geocoding (8)
Esta es más una pregunta de desafío que algo que necesito urgentemente, así que no pasen todo el día en eso chicos.
Construí un sitio de citas (hace mucho tiempo atrás) en 2000 o algo así, y uno de los desafíos fue calcular la distancia entre los usuarios para que pudiéramos presentar sus "coincidencias" dentro de un radio de X millas. Para simplemente indicar el problema, dado el siguiente esquema de base de datos (más o menos):
TABLA DE USUARIO UserId UserName ZipCode
MESA ZIPCODE Código postal Latitud Longitud
Con USER y ZIPCODE unidos en USER.ZipCode = ZIPCODE.ZipCode.
¿Qué enfoque tomaría para responder la siguiente pregunta: qué otros usuarios viven en códigos postales que están dentro de X millas del código postal de un usuario determinado.
Usamos los datos del censo 2000 , que tiene tablas para códigos postales y su latitud y longitud aproximadas.
También usamos la Fórmula Haversine para calcular las distancias entre dos puntos en una esfera ... realmente muy simple.
La pregunta, al menos para nosotros, siendo los estudiantes universitarios de 19 años que éramos, realmente se convirtió en cómo calcular de forma eficiente y / almacenar las distancias de todos los miembros a todos los demás miembros. Un enfoque (el que utilizamos) sería importar todos los datos y calcular la distancia DESDE cada código postal A todos los demás códigos postales. Luego, almacenarías e indexarías los resultados. Algo como:
SELECT User.UserId
FROM ZipCode AS MyZipCode
INNER JOIN ZipDistance ON MyZipCode.ZipCode = ZipDistance.MyZipCode
INNER JOIN ZipCode AS TheirZipCode ON ZipDistance.OtherZipCode = TheirZipCode.ZipCode
INNER JOIN User AS User ON TheirZipCode.ZipCode = User.ZipCode
WHERE ( MyZipCode.ZipCode = 75044 )
AND ( ZipDistance.Distance < 50 )
El problema, por supuesto, es que la tabla ZipDistance va a tener MUCHAS filas en ella. No es completamente inviable, pero es realmente grande. También requiere pre-trabajo completo en todo el conjunto de datos, que tampoco es inmanejable, pero no necesariamente deseable.
De todos modos, me preguntaba qué enfoque podrían tomar algunos de ustedes, los gurús en algo como esto. Además, creo que este es un problema común que los programadores deben abordar de vez en cuando, especialmente si se consideran problemas que son algorítmicamente similares. Estoy interesado en una solución completa que incluya al menos HINTS en todas las piezas para que esto termine rápidamente. ¡Gracias!
No se usarán todos los códigos postales posibles. Construiría zipdistance como una tabla de ''caché''. Para cada solicitud, calcule la distancia para ese par y guárdela en el caché. Cuando llega una solicitud de par de distancia, primero busque en la caché, luego calcule si no está disponible.
No conozco las complejidades de los cálculos de distancia, por lo que también verificaría si la computación sobre la marcha es más económica que la búsqueda (también teniendo en cuenta la frecuencia con la que debe calcular).
Ok, para empezar, realmente no necesitas usar la fórmula Haversine aquí. Para distancias grandes donde una fórmula menos precisa produce un error mayor, a sus usuarios no les importa si la coincidencia es más o menos unas pocas millas, y para distancias más cercanas, el error es muy pequeño. Hay fórmulas más fáciles (para calcular) enumeradas en el artículo de Geographical Distance Wikipedia.
Debido a que los códigos postales no tienen el mismo espacio, cualquier proceso que los divida en partes iguales sufrirá enormemente en áreas donde están agrupados (la costa este cerca de DC es un buen ejemplo). Si desea una comparación visual, consulte http://benfry.com/zipdecode y compare el prefijo de código postal 89 con 07.
Una forma mucho mejor de lidiar con la indexación de este espacio es usar una estructura de datos como un Quadtree o un R-tree . Esta estructura le permite realizar búsquedas espaciales y de distancia sobre datos que no están espaciados uniformemente.
Así es como se ve un Quadtree:
Para buscar sobre ella, profundiza a través de cada celda más grande usando el índice de celdas más pequeñas que están dentro de ella. Wikipedia lo explica más a fondo.
Por supuesto, ya que esto es algo bastante común de hacer, alguien más ya ha hecho la parte difícil para usted. Como no ha especificado qué base de datos está utilizando, la extensión PostgreSQL PostGIS servirá como ejemplo. PostGIS incluye la capacidad de hacer índices espaciales de árbol R que le permiten hacer consultas espaciales eficientes.
Una vez que haya importado sus datos y construido el índice espacial, consultar la distancia es una consulta como:
SELECT zip
FROM zipcode
WHERE
geom && expand(transform(PointFromText(''POINT(-116.768347 33.911404)'', 4269),32661), 16093)
AND
distance(
transform(PointFromText(''POINT(-116.768347 33.911404)'', 4269),32661),
geom) < 16093
Te dejaré trabajar el resto del tutorial tú mismo.
Aquí hay otras referencias para comenzar.
Podría atajar el cálculo simplemente asumiendo un cuadro en lugar de un radio circular. Luego, cuando busque, simplemente calcule el límite inferior / superior de lat / lon para un punto dado + "radio", y siempre que tenga un índice en las columnas lat / lon podría retirar todos los registros que caen dentro del cuadro con bastante facilidad .
Podrías dividir tu espacio en regiones de aproximadamente el mismo tamaño, por ejemplo, aproximar la Tierra como buckyball o icosaedro. Las regiones podrían incluso superponerse un poco, si es más fácil (por ejemplo, hacerlas circulares). Registre en qué región (s) está cada código postal. Luego puede precalcular la distancia máxima posible entre cada par de regiones, que tiene el mismo problema O (n ^ 2) que calcular todos los pares de códigos postales, pero para n más pequeños.
Ahora, para cualquier código postal dado, puede obtener una lista de regiones que están definitivamente dentro de su rango dado, y una lista de regiones que cruzan el límite. Para el primero, simplemente agarre todos los códigos postales. Para este último, profundice en cada región fronteriza y calcule contra códigos postales individuales.
Sin duda es más complejo matemáticamente y, en particular, debería elegirse el número de regiones para lograr un buen equilibrio entre el tamaño de la tabla y el tiempo dedicado a calcular sobre la marcha, pero reduce el tamaño de la tabla precalculada por un buen margen.
Sé que esta publicación es DEMASIADO viejo, pero haciendo algunas investigaciones para un cliente. He encontrado algunas funcionalidades útiles de la API de Google Maps y es tan simple de implementar que solo necesita pasar a la URL los códigos postales de origen y de destino, y calcula la distancia incluso con el tráfico, puede usarlo con cualquier idioma:
origins = 90210
destinations = 93030
mode = driving
siguiendo el enlace puede ver que devuelve un json. Recuerde que necesita una clave API para usar esto en su propio hosting.
Simplemente crearía una tabla zip_code_distances y calcularía previamente las distancias entre todos los códigos postales 42K en los EE. UU. Que se encuentran dentro de un radio de 20-25 millas entre sí.
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;
La inclusión de códigos postales dentro de un radio de 20-25 millas reduce la cantidad de filas que necesita almacenar en la tabla de distancias, desde un máximo de 1.700 millones (42K ^ 2) - 42K hasta 4 millones más manejables.
Descargué un archivo de datos de código postal de la web que contenía las longitudes y latitudes de todos los códigos postales oficiales de EE. UU. En formato 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
...
Escribí un programa C # rápido y sucio para leer el archivo y calcular las distancias entre cada código postal, pero solo obtuve códigos postales que caen dentro de un radio de 25 millas:
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);
}
}
El archivo de salida resultante se ve de la siguiente manera:
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
...
Entonces, simplemente cargaba estos datos de distancia en mi tabla zip_code_distances utilizando load data infile y luego la uso para limitar el espacio de búsqueda de mi aplicación.
Por ejemplo, si tiene un usuario cuyo código postal es 91210 y quiere encontrar personas que se encuentren dentro de un radio de 10 millas de ellos, ahora puede hacer lo siguiente:
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''....
Espero que esto ayude
EDITAR: radio extendido a 100 millas que aumentó el número de distancias de código postal a 32.5 millones de filas.
comprobación de rendimiento rápido para el código de tiempo de ejecución de 91210 0.009 segundos.
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
Tengo el problema funcionando a la perfección, y casi toda la respuesta se usó. Estaba pensando en esto en términos de la vieja solución en lugar de solo "empezar de nuevo". Babtek recibe el visto bueno por declarar en términos más simples.
Voy a omitir el código porque proporcionaré referencias para derivar las fórmulas necesarias, y hay mucho para publicar aquí limpiamente.
1) Considere el punto A en una esfera, representada por latitud y longitud. Calcule los bordes Norte, Sur, Este y Oeste de una caja de 2x millas de ancho con el Punto A en el centro .
2) Seleccione todo el punto dentro del cuadro de la tabla ZipCode. Esto incluye una cláusula WHERE simple con dos declaraciones Between que limitan por Lat y Long.
3) Use la fórmula de haversine para determinar la distancia esférica entre el punto A y cada punto B devuelto en el paso 2.
4) Deseche todos los puntos B donde la distancia A -> B> X.
5) Seleccione usuarios donde ZipCode esté en el conjunto restante de puntos B.
Esto es bastante rápido para> 100 millas. El resultado más largo fue ~ 0.014 segundos para calcular la coincidencia, y trivial para ejecutar la declaración de selección.
Además, como nota al margen, fue necesario implementar las matemáticas en un par de funciones y llamarlas en SQL. Una vez que pasé de cierta distancia, el número coincidente de ZipCodes era demasiado grande para volver a SQL y usarlo como una declaración IN, así que tuve que usar una tabla temporal y unir los ZipCodes resultantes al usuario en la columna ZipCode.
Sospecho que usar una tabla ZipDistance no proporcionará una ganancia de rendimiento a largo plazo. La cantidad de filas es realmente grande. Si calcula la distancia desde cada código postal a cada otro código postal (eventualmente), el conteo de fila resultante de 40,000 códigos postales sería ~ 1.6B. Whoah!
Alternativamente, estoy interesado en usar el tipo de geografía incorporada de SQL para ver si eso lo hará más fácil, pero los buenos viejos tipos de int / float sirven bien para esta muestra.
Entonces ... la lista final de recursos en línea que utilicé, para su fácil referencia:
1) Diferencia máxima, latitud y longitud .
2) La fórmula Haversine .
3) Discusión larga pero completa de todo el proceso , que encontré de las cosas en Google en tus respuestas.
Yo usaría la latitud y la longitud. Por ejemplo, si tiene una latitud de 45 y una longitud de 45 y se le pidió que buscara coincidencias dentro de las 50 millas, entonces podría hacerlo moviéndose 50/69 en latitud y 50/69 en latitud (1 grado). latitud ~ 69 millas). Seleccione códigos postales con latitudes en este rango. Las longitudes son un poco diferentes, porque se hacen más pequeñas a medida que te acercas a los polos.
Pero a 45 grados, 1 longitud ~ 49 millas, por lo que podría mover 50/49 en la latitud y 50/49 en la latitud, y seleccionar todos los códigos postales de la latitud establecida con esta longitud. Esto le da todos los códigos postales dentro de un cuadrado con longitudes de cien millas. Si quieres ser realmente preciso, puedes usar la fórmula de Haversine que mencionaste para eliminar las cremalleras en las esquinas de la caja, para darte una esfera.