Cómo almacenar la distancia entre ciudades en BD de manera eficiente

Question

Necesito poder mostrar la distancia a n ciudades/pueblos desde una ubicación particular elegida por el usuario. Es como hacer clic en un mapa y obtener todos los destinos dentro de las 100 millas, solo que no será un mapa sino un enlace en la página web.

Necesito elegir una solución que amplíe desde un estado a un país a nivel mundial potencialmente, lo que significa de mil a cientos de miles de ubicaciones.

Pensé en almacenar CITY1_ID, CITY2_ID & DISTANCE en una tabla de DB relacional, pero dudo si se escalara bien para una aplicación web (millones de filas).

¿Se podría hacer esto de manera más eficiente usando una base de datos NoSQL o una base de datos gráfica? ¿O es RDBMS lo suficientemente bueno para este problema con un diseño adecuado?

Agregado: Si no almaceno en DB, entonces ¿cómo obtendré algo así como: Conseguirme todas las ciudades dentro de las 100 millas de San Jose?

Answer 1

debe almacenar city_id, latitude, longitude uno para cada ciudad - luego calcule las distancias según la entrada del tiempo de ejecución.

Answer 2

No lo almacene, calcule el tiempo de ejecución con la longitud y la latitud. Extremadamente escalable, al contrario de guardar todas las distancias entre ciudades.

Tiene un punto de referencia (San Jose) y recorre todos los registros de su ciudad y calcula su tiempo de ejecución (en el caso de muchos registros, realice este cálculo por el cliente, probablemente con javascript o algo similar, porque si tiene el servidor lo hace, costará su peaje demasiado pronto). El JavaScript podría ser algo como esto:

var R = 6371; // Radius of the earth in km 
var dLat = (lat2-lat1).toRad(); // Javascript functions in radians 
var dLon = (lon2-lon1).toRad(); 
var a = Math.sin(dLat/2) * Math.sin(dLat/2) + 
     Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * 
     Math.sin(dLon/2) * Math.sin(dLon/2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c; // Distance in km 

Por encima de código proviene de here

Nota: Es en kilómetros como yo soy holandés y por lo tanto con el sistema métrico

Answer 3

estoy usando Neo4J por algo similar, se adapta muy bien para cualquier tipo de datos que puedan representarse como un gráfico.

Answer 4

Se podría, como han dicho otros, almacenar las coordenadas de latitud/longitud para cada entrada y calcular la distancia usando algo similar al siguiente en tiempo de ejecución, lo que proporciona km/millas salida distancia:

function distance($lat1, $lng1, $lat2, $lng2, $miles = true) 
{ 
     $pi80 = M_PI/180; 
     $lat1 *= $pi80; 
     $lng1 *= $pi80; 
     $lat2 *= $pi80; 
     $lng2 *= $pi80; 

     $r = 6372.797; // mean radius of Earth in km 
     $dlat = $lat2 - $lat1; 
     $dlng = $lng2 - $lng1; 
     $a = sin($dlat/2) * sin($dlat/2) + cos($lat1) * cos($lat2) * sin($dlng/2) * sin($dlng/2); 
     $c = 2 * atan2(sqrt($a), sqrt(1 - $a)); 
     $km = $r * $c; 

     return ($miles ? ($km * 0.621371192) : $km); 
} 

EDITAR : Esto no es adecuado para n coincidencias dentro de una búsqueda de radio. Dada la densidad de pueblos/ciudades dentro de un radio dado, es mejor mover los cálculos de distancia a SQL ya que es mucho más rápido y puede hacer coincidir los de dentro de x km/millas.

Answer 5

Un sencilla solución que he usado varias veces (pero no con MySQL) es crear un usuario some_distance_function función definida con cuatro parámetros latitude1, longitude1, latitude2, longitude2 que devuelve la distancia y luego simplemente probar todo contra esa distancia función y ver para cada elemento, independientemente de si la distancia es menor o igual que un valor determinado. Si solo va a tener unos miles de ubicaciones, esto es bastante bueno y eficiente.

Si necesita ejecutar esta consulta contra millones de registros, es posible que desee ver qué extensiones SIG (Geography Information Systems) están disponibles para su base de datos de elección, ya que hay mejores (al menos en términos de búsqueda-capacidad) estructuras de datos persistentes para buscar en un gran número de ubicaciones.

Editar: Para dar un ejemplo de cómo Microsoft lo hace, ver http://technet.microsoft.com/en-us/library/bb964712(v=sql.105).aspx

Parece que MySQL soporta extensiones espaciales en general:

http://dev.mysql.com/doc/refman/5.0/en/gis-introduction.html
http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html

Editar II:

Parece que esta pregunta también podría ser útil.

Find the distance between two points in MYSQL. (using the Point Datatype)

Answer 6

Aquí es una solución usando RDBMS. Mantener dos mesas

• CityByLat {latitud, city_id} con índice agrupado en latitud y
• CityByLng {logitude, city_id} con índice agrupado en longitud

Cuando es necesario encontrar ciudades dentro de un cierto radio de una latitud y longitud dada, puede hacer una consulta de rango eficiente en las dos tablas para obtener ciudades dentro de un cierto rango de latitud y longitud. A continuación, puede calcular la distancia real solo desde las ciudades recuperadas.

Answer 7

En lugar de calcular la distancia entre las 2 ciudades, calcule un cuadro delimitador de 100 millas y luego tenga 4 variables flotantes para conectar a su base de datos. La comparación flotante es mucho más rápida que los cálculos de distancia en la base de datos. Lo malo es que tienes un poco más de distancia en las curvas.

función de PHP para calcular cuadro

 
function getBoundingBox($lat_degrees,$lon_degrees,$distance_in_miles) 
{ 
     $radius = 3963.1; // of earth in miles 

     // bearings 
     $due_north = 0; 
     $due_south = 180; 
     $due_east = 90; 
     $due_west = 270; 

     // convert latitude and longitude into radians 
     $lat_r = deg2rad($lat_degrees); 
     $lon_r = deg2rad($lon_degrees); 

     // find the northmost, southmost, eastmost and westmost corners $distance_in_miles away 
     // original formula from 
     // http://www.movable-type.co.uk/scripts/latlong.html 

     $northmost = asin(sin($lat_r) * cos($distance_in_miles/$radius) + cos($lat_r) * sin ($distance_in_miles/$radius) * cos($due_north)); 
     $southmost = asin(sin($lat_r) * cos($distance_in_miles/$radius) + cos($lat_r) * sin ($distance_in_miles/$radius) * cos($due_south)); 

     $eastmost = $lon_r + atan2(sin($due_east)*sin($distance_in_miles/$radius)*cos($lat_r),cos($distance_in_miles/$radius)-sin($lat_r)*sin($lat_r)); 
     $westmost = $lon_r + atan2(sin($due_west)*sin($distance_in_miles/$radius)*cos($lat_r),cos($distance_in_miles/$radius)-sin($lat_r)*sin($lat_r)); 

     $northmost = rad2deg($northmost); 
     $southmost = rad2deg($southmost); 
     $eastmost = rad2deg($eastmost); 
     $westmost = rad2deg($westmost); 

     //return 2 points NW corner and SE corner 
     return array($northmost,$westmost,$southmost,$eastmost); 
} 

que limita entonces su SQL es

SELECT * FROM table WHERE latitude <= $northmost AND longitude >= $westmost AND latitude >= $southmost AND longitude <= $eastmost