Proximity Search

Question

Wie führt eine Anwendung eine Proximity-Suche aus? Wenn ein Benutzer beispielsweise eine Postleitzahl eingibt, listet die Anwendung alle Geschäfte auf, die sich in der Nähe von 20 Meilen befinden.

Ich möchte so etwas in PHP und MySQL erstellen. Ist dieser Ansatz richtig?

1. Holen Sie sich die Adressen für Standorte Ich habe Interesse an und speichern Sie in meiner Datenbank
2. Geocode alle Adressen mit Googles Geocodierungsdienst
3. eine Datenbankabfrage schreiben, die Haversine Formel beinhaltet die Umkreissuche und Bestellung zu tun

Ist das OK? In Schritt 3 werde ich die Nähe für jede Abfrage berechnen. Ist es besser, eine PROXIMITY-Tabelle zu haben, die die Entfernung zwischen jedem Unternehmen und einigen Referenzstandorten auflistet?

Answer 1

Wenn genügend Datensätze für die Geschwindigkeit vorhanden sind, können Sie sie im Voraus indizieren.

Definieren Sie ein Gitter von Behältern etwa 20 Meilen auf einer Seite. Speichern Sie die Fachnummer mit jedem Geschäftsdatensatz. Berechnen Sie zur Suchzeit die Nummern aller Fächer, die einen 20-Meilen-Radius von Ihrem Suchpunkt schneiden. Rufen Sie dann alle Geschäfte in einem dieser Fächer ab und fahren Sie wie zuvor fort.

Answer 2

Wir tun dies für etwa 1200 Standorte. Ich würde einfach die Haversine-Formel im laufenden Betrieb verwenden, obwohl es je nach Ihrer Anwendung besser ist, sie in PHP anstatt in SQL zu speichern. (Unsere Implementierung ist in .net, so dass Ihre Kilometer variieren können).

Wirklich unser größter Nachteil bei der Art und Weise, wie wir es implementiert haben, ist, dass jede Berechnung (bis vor kurzem) auf der Datenebene berechnet werden musste, die schmerzhaft langsam war (wenn ich langsam sage, ich meine wirklich nicht sofort eine Sekunde oder so), aber das war aufgrund der Tatsache, dass es die Entfernung für alle 1200 Standorte basierend auf der gelieferten Postleitzahl berechnen musste.

Je nach gewählter Route gibt es Möglichkeiten, die Berechnung der Entfernung zu beschleunigen, indem Sie Längen- und Breitengrad betrachten und Entfernungen außerhalb eines vordefinierten Bereichs entfernen (wenn Sie beispielsweise alle Adressen innerhalb von 20 sehen) Meilen gibt es einen Längenbereich, den Sie berechnen können, die alle Adressen haben müssen, um 20 Meilen weg zu sein.) Das kann Ihre Frage beschleunigen, wenn es sein muss.

Wir haben tatsächlich alle möglichen Kombinationen in unserer Datenbank gespeichert. In der Realität hört es sich an, als könnte es ein großer Datenspeicher sein, aber es ist wirklich nicht im großen Umfang der Dinge. Mit Indizes kann es ziemlich schnell sein, und Sie müssen sich keine Sorgen um Algorithmusoptimierung usw. machen. Wir haben uns dagegen entschieden, weil wir die Gleichung in C# hatten, und es uns erlaubte, die Informationen zu speichern, die für alle Berechnungen benötigt werden Geschäftsstufe. Beides wird gut funktionieren, es kommt nur darauf an, was Sie bevorzugen.

Answer 3

Wir verwenden dies, um viele tausend Punkte zu machen. Es ist wichtig, wenn Sie dies in SQL ausführen, um einen Index für die Spalte Breite und Länge zu haben. Wir haben dies in SQL 2008 mit räumlichen Indizes versucht, aber wir haben die erwartete Leistungssteigerung nicht wirklich gesehen. Wenn Sie jedoch innerhalb einer bestimmten Entfernung von einer ZIP-Datei berechnen möchten, müssen Sie darüber nachdenken, ob Sie den ZIP-Schwerpunkt oder eine Polygondarstellung der Postleitzahl verwenden möchten.

Haversine forumla ist ein guter Anfang.

Wir hatten keine Leistungsprobleme bei der Berechnung der Entfernung im laufenden Betrieb, wir berechnen es im Voraus für einige Anwendungen, wo wir die Punkte im Voraus kennen und es wird Millionen von Datensätzen geben.

SELECT 
     [DistanceRadius]= 
     69.09 * 
     DEGREES(
      ACOS(
      SIN(RADIANS(latitude))*SIN(RADIANS(@ziplat)) 
      + 
      COS(RADIANS(latitude))*COS(RADIANS(@ziplat)) 
      * 
      COS(RADIANS(longitude - (@ziplon))) 
     ) 
     ) 
     ,* 
     FROM 
      table 

    ) sub 
WHERE 
    sub.DistanceRadius < @radius