Umkreissuche mit Lucene
12_2011
In einem aktuellen Projekt haben wir eine Suche nach freien Pflegeplätzen in Hamburg und dem angrenzenden Umland umgesetzt.
Das Konzept sah eine Umkreissuche vor. Das Budget verlangte, dass die Suche sich mit wenig Aufwand realisieren lassen sollte.
Die Aufgabe
Im Interface für die Suche wählen die User entweder einen Ort auf einer Karte aus oder sie geben eine Adresse postalisch als Strasse und Ort ein. Anschliessend entscheiden sie sich für einen Radius. Als Ergebnis werden alle freien Pflegeplätze angezeigt, die sich im gewählten Umkreis befinden.
Für diese Anwendung ist es nicht wichtig, dass die Ergebnisse sich *exakt* im gewählten Radius befinden. Der Umkreis stellt nur eine Annäherung dar; ob sich ein Objekt im 5 km-Radius oder im 6,75 km-Radius befindet, ist für den Nutzen der Suche unerheblich.
Daher können wir – anstatt die Objekte auf einen Kreis einzuschränken – einen Bounding-Box-Ansatz benutzen, der alle Objekte findet, die innerhalb eines Rechtecks liegen. Bounding Box ist algorithmisch einfacher als das Einschränken auf einen exakten Radius. Wenn die Ergebnisse wieder auf einer Karte dargestellt werden, ist der Bounding-Box-Ansatz für die User auch nützlicher, weil im Ergebnis alle Objekte enthalten sind, die sich im jeweiligen Kartenausschnitt finden.
Lucene oder relationale Datenbank
Da wir die Pflegeheime nicht als Objekte in einer relationalen Datenbank vorliegen haben (sie werden als generische Content-Objekte im CMS gespeichert) und die gesamte Suche im Projekt mit Lucene implementiert wurde, haben wir uns dafür entschieden, auch für die Umkreissuche Lucene einzusetzen.
Berechnung
Aus der Wikipedia haben wir entnommen, dass zwei Breitengrade immer einen Abstand von 111 km haben, während der Abstand der Längengrade mit der geographischen Breite variiert. Am Äquator ist der Abstand zwischen den Längengraden am größten, am Pol laufen sie in einem Punkt zusammen.
Für Deutschland gilt, dass die Abstände der Längengrade zwischen etwa 75 km ganz im Süden und 64 km ganz im Norden laufen. Wir nehmen für Hamburg und Umgebung daher näherungsweise 66 km pro Längengrad an.
Die Adressen der Pflegeheime liegen nur postalisch vor. Für die Umkreissuche haben wir uns mit Hilfe der Google-Geocoding-API[1] die entsprechenden Koordinaten besorgt und sie im Lucene-Index gespeichert.
Die Eingabe der User überführen wir ebenfalls mit dem Google Geocoder in Koordinaten. Für die Suche nach Objekten in der Nähe ist dann nur noch das Bestimmen der Rechteck-Grenzen und eine einfache Range-Search in Lucene nötig:
left = center_lng - 1/66 * radius
right = center_lng + 1/66 * radius
bottom = center_lat + 1/111 * radius
top = center_lat + 1/111 * radius
latitude:[<bottom> TO <top>]) longitude:[<left> TO <right>]
Mit dieser Lösung ist es ohne viel Aufwand möglich, bestehende Lucene-Suchen um einen Umkreis-Filter zu erweitern.