Come memorizzare efficientemente la distanza tra città e paesi in DB

Question

Devo essere in grado di visualizzare la distanza a n città/paesi da una particolare località scelta dall'utente. È come cliccare su una mappa e ottenere tutte le destinazioni entro 100 miglia, solo che non sarà una mappa ma un link sulla pagina web.

Ho bisogno di scegliere una soluzione che passi da uno stato all'altro in un paese potenzialmente globale - il che significa da mille a centomila località.

Mi sembra di memorizzare CITY1_ID, CITY2_ID & DISTANCE in una tabella DB relazionale, ma dubito che sarebbe scalabile per un'applicazione Web (milioni di righe).

Questa operazione può essere eseguita in modo più efficiente utilizzando un database NoSQL o un DB grafico? O è RDBMS abbastanza buono per questo problema con una corretta progettazione?

Aggiunto: Se non memorizzo in DB, allora come otterrò qualcosa del tipo: Portami tutte le città entro 100 miglia da San Jose?

Answer 1

è necessario memorizzare city_id, latitude, longitude uno per ogni città, quindi calcolare le distanze in base all'input di runtime.

Answer 2

Non memorizzarlo, calcolarlo in runtime con longitudine e latitudine. Estremamente scalabile, contrariamente a salvare tutte le distanze tra le città.

Si dispone di un punto di riferimento (San Jose) e si collegano tutti i record della città e si calcola il tempo di esecuzione (in caso di molti record, questo calcolo viene eseguito dal client, probabilmente con javascript o qualcosa del genere, perché se si dispone del server lo faccia, costerà il suo tributo troppo presto). Il codice JavaScript potrebbe essere simile a questo:

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 

Sopra il codice viene da here

Nota: E 'in chilometri come io sono olandese e utilizzando quindi il sistema metrico

Answer 3

Sto usando Neo4J per qualcosa simile, si adatta molto bene a qualsiasi tipo di dati che possono essere rappresentati come un grafico.

Answer 4

Si potrebbe, come altri hanno notato, memorizzare i/coordinate lungo Lat per ogni voce e calcolare la distanza utilizzando qualcosa di simile a quanto segue in fase di esecuzione, che fornisce km/miglia uscita distanza:

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); 
} 

EDIT : Non è adatto per le corrispondenze n all'interno di una ricerca di raggio. Data la densità delle città/città all'interno di un determinato raggio, è meglio spostare i calcoli della distanza in SQL come molto più veloce e puoi confrontare quelli all'interno di x km/miglia.

Answer 5

Un semplice soluzione che ho usato più volte (ma non con mysql) è creare un utente funzione some_distance_function definita con quattro parametri latitude1, longitude1, latitude2, longitude2 che restituisce la distanza e poi basta testano tutto contro quella distanza funzione e vedere per ogni articolo, indipendentemente dal fatto che la distanza sia inferiore o uguale a un determinato valore. Se hai solo poche migliaia di posizioni, questo è abbastanza buono ed efficiente.

Se è necessario eseguire questa query su milioni di record, si potrebbe voler vedere quali estensioni GIS (Geography Information Systems) sono disponibili per il database di scelta, poiché ci sono migliori (almeno in termini di capacità di ricerca) strutture di dati persistenti per la ricerca attraverso un vasto numero di posizioni.

Edit: Per dare un esempio di come Microsoft lo fa, si veda http://technet.microsoft.com/en-us/library/bb964712(v=sql.105).aspx

Sembra che MySQL supporta le estensioni spaziali in generale:

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

Edit II:

Sembra che questa domanda potrebbe anche essere utile.

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

Answer 6

Ecco una soluzione che utilizza RDBMS. Mantenere due tavoli

• CityByLat {latitudine, city_id} con indice cluster in latitudine e
• CityByLng {logitude, city_id} con indice cluster longitudine

Quando hai bisogno di trovare le città una determinata raggio da una data latitudine e longitudine è possibile eseguire una query di intervallo efficiente sulle due tabelle per ottenere città entro un determinato intervallo di latitudine e longitudine. È quindi possibile calcolare la distanza effettiva solo dalle città così recuperate.

Answer 7

Invece di calcolare la distanza tra le 2 città calcolare un riquadro di delimitazione di 100 miglia, è necessario inserire 4 variabili float nel database: il confronto float è molto più veloce dei calcoli della distanza nel database. Il rovescio della medaglia è che si ottiene un po 'più di distanza negli angoli.

funzione PHP per calcolare scatola

 
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); 
} 

delimitazione allora il vostro SQL è

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