So speichern Sie die Entfernung zwischen Städten und Gemeinden in der DB effizient

Question

Ich muss in der Lage sein, die Entfernung zu n Städte von einem bestimmten Ort durch den Benutzer ausgewählt anzuzeigen. Es ist so, als würde man auf eine Karte klicken und alle Ziele innerhalb von 100 Meilen erreichen, nur dass es sich nicht um eine Karte, sondern um einen Link auf der Webseite handelt.

Ich muss eine Lösung wählen, die von einem Staat zu einem Land global potentiell hochskaliert - also von tausend bis hunderttausend Standorten.

Ich habe zwar CITY1_ID, CITY2_ID & DISTANCE in einer relationalen DB-Tabelle gespeichert, aber ich bezweifle, ob es gut für eine Webanwendung (Millionen von Zeilen) skalieren würde.

Könnte dies mit einer NoSQL-Datenbank oder Graph-DB effizienter gemacht werden? Oder ist RDBMS mit dem richtigen Design gut genug für dieses Problem?

Hinzugefügt: Wenn ich nicht in DB speichern dann wie bekomme ich etwas wie: Hol dir alle Städte im Umkreis von 100 Meilen von San Jose?

Answer 1

Sie sollten city_id, latitude, longitude eine für jede Stadt speichern - dann berechnen Sie die Entfernungen basierend auf Laufzeiteingabe.

Answer 2

Nicht speichern, berechnen Sie die Laufzeit mit Längen- und Breitengrad. Extrem skalierbar, im Gegensatz zur Speicherung aller Entfernungen zwischen den Städten.

Sie haben einen Bezugspunkt (San Jose) und durchlaufen Sie alle Ihre Stadt Aufzeichnungen und Berechnung es Laufzeit (im Falle von vielen Aufzeichnungen, haben diese Berechnung vom Client durchgeführt, wahrscheinlich mit Javascript oder etwas, denn wenn Sie die Server tun es, es wird viel zu früh seinen Zoll kosten). Die JavaScript könnte wie folgt aussehen:

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 

Above Code stammt aus here

Hinweis: in Kilometern ist wie ich Holländer bin und somit mit dem metrischen System

Answer 3

Ich verwende Neo4J für etwas Ähnlich skaliert es wirklich gut für jede Art von Daten, die als Graph dargestellt werden können.

Answer 4

Sie könnten, wie andere hier schon berichtet haben, speichern Sie die Breite/Länge coords für jeden Eintrag und berechnen den Abstand etwas mit ähnlich wie die zur Laufzeit folgt, die km/Meilen Entfernung Ausgang liefert:

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 : Dies ist nicht geeignet für n Übereinstimmungen innerhalb eines Radius suchen. Angesichts der Dichte der Städte in einem bestimmten Radius, besser die Entfernungsberechnungen in SQL zu verschieben, da es viel schneller ist und Sie mit denen innerhalb x km/Meilen übereinstimmen können.

Answer 5

A einfache Lösung, die ich mehrfach verwendet haben (aber nicht mit mysql) ist eine Benutzerfunktion some_distance_function mit vier Parametern latitude1, longitude1, latitude2, longitude2 definiert zu schaffen, die den Abstand zurück und testen Sie dann einfach alles gegen diese Entfernung Funktion und sehen Sie für jedes Element, ob die Entfernung kleiner oder gleich einem bestimmten Wert ist. Wenn Sie nur ein paar tausend Standorte haben, ist das ziemlich gut und effizient.

Wenn Sie diese Abfrage gegen Millionen von Datensätzen ausführen müssen, möchten Sie möglicherweise sehen, welche GIS (Geography Information Systems) -Erweiterungen für Ihre bevorzugte Datenbank verfügbar sind, da sie besser sind (zumindest in Bezug auf die Suchfunktion)) persistente Datenstrukturen für die Suche über eine große Anzahl von Standorten.

Edit: Um ein Beispiel zu geben, wie Microsoft es tut, siehe http://technet.microsoft.com/en-us/library/bb964712(v=sql.105).aspx

Es ist wie MySQL sieht räumliche Erweiterungen im Allgemeinen unterstützt:

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

bearbeiten II:

Sieht aus wie diese Frage auch hilfreich sein könnte.

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

Answer 6

Hier ist eine Lösung RDBMS verwenden. Halten Sie zwei Tabellen

• CityByLat {Breitengrad, city_id} mit Clustered-Index für Breiten- und
• CityByLng {logitude, city_id} mit Clustered-Index auf Länge

Wenn Sie innerhalb einer bestimmten Städten finden müssen Radius von einem gegebenen Breiten- und Längengrad Sie können eine effiziente Bereichsabfrage an den beiden Tabellen durchführen, um Städte innerhalb eines bestimmten Längen- und Breitengrads zu erhalten. Sie können dann die tatsächliche Entfernung von nur den so abgerufenen Städten berechnen.

Answer 7

Anstatt die Entfernung zwischen den 2 Städten zu berechnen, berechnen Sie eine Bounding Box von 100 Meilen, dann haben Sie 4 Float Variablen in Ihre Datenbank zu stecken - Float Vergleich ist viel schneller als Entfernungsberechnungen in der Datenbank. Nachteil ist, dass Sie in den Ecken etwas mehr Abstand haben.

PHP-Funktion zu berechnen Begrenzungsrahmen

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

dann SQL ist

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