Verwenden Sie Geohash für die Umkreissuche?

Ich möchte die Geo-Suchzeit für die Punktnähe optimieren.

Meine Eingabe ist lat, lng point und ich suche auf einer vorberechneten Menge von Orten nach n nächstgelegenen Punkten.

Es ist mir egal, wie viel Zeit / Raum der Aufbau des vorberechneten Ortsindex benötigt, aber es ist mir wichtig, dass die Abfragen superschnell sind.

Ich denke darüber nach, Geohash als Suchschlüssel zu verwenden. Dabei überprüfe ich zunächst, ob ich Ergebnisse für X Zeichen des Schlüssels erhalte, und schneide dann die Zeichen ab dem Ende des Schlüssels weiter ab, bis die Ergebnisse angezeigt werden.

Nach meinem (noch sehr spärlichen) Verständnis der Geo-Index-Techniken sollte dieser Ansatz im Vergleich zu allen anderen bekannten Implementierungen (wie R Tree und Co.) die schnellsten Ergebnisse (in Bezug auf die Abfragezeit) liefern können.

Absolut kannst du. Und es kann ziemlich schnell gehen. (Die intensiven Rechenbits können AUCH verteilt werden)

Es gibt mehrere Möglichkeiten, aber eine Möglichkeit, mit der ich gearbeitet habe, besteht darin, eine geordnete Liste ganzzahliger Geohashes zu verwenden und alle nächsten Geohash-Bereiche für eine bestimmte Geohash-Auflösung zu ermitteln (die Auflösung entspricht in etwa Ihren distanceKriterien) Abfragen dieser Geohash-Bereiche, um eine Liste von Punkten in der Nähe zu erhalten. Ich benutze dafür Redis und Nodejs (zB Javascript). Redis ist superschnell und kann geordnete Bereiche sehr schnell abrufen, kann jedoch nicht viele der Aufgaben zur Bearbeitung von Indexabfragen ausführen, die SQL-Datenbanken ausführen können.

Die Methode wird hier beschrieben: https://github.com/yinqiwen/ardb/wiki/Spatial-Index

Aber der Kern davon ist (um den Link zu paraphrasieren):

1. Sie speichern alle Ihre geohashten Punkte in der bestmöglichen Auflösung (in der Regel 64-Bit-Ganzzahl, falls verfügbar, oder bei Javascript 52 Bit) in einem geordneten Satz (zset in redis). In den meisten Geohash-Bibliotheken sind heutzutage Geohash-Integer-Funktionen integriert, und Sie müssen diese anstelle der allgemeineren Base32-Geohashes verwenden.
2. Basierend auf dem Radius, in dem Sie suchen möchten, müssen Sie dann eine Bittiefe / Auflösung finden, die Ihrem Suchbereich entspricht und die kleiner oder gleich Ihrer gespeicherten Geohash-Bittiefe sein muss. Die verknüpfte Site verfügt über eine Tabelle, die die Bittiefe einer Geohash mit der Begrenzungsrahmenfläche in Metern korreliert.
3. Dann wärmen Sie Ihre ursprüngliche Koordinate mit dieser niedrigeren Auflösung auf.
4. Bei dieser niedrigeren Auflösung finden Sie auch die 8 benachbarten (n, ne, e, se, s, sw, w, nw) Geohash-Bereiche. Der Grund, warum Sie die Nachbarmethode ausführen müssen, besteht darin, dass zwei Koordinaten, die nahezu nebeneinander liegen, völlig unterschiedliche Geohashes aufweisen können. Daher müssen Sie eine Mittelung des von der Suche abgedeckten Bereichs vornehmen.
5. Wenn Sie alle Geohashes der Nachbarn mit dieser niedrigeren Auflösung erhalten haben, fügen Sie der Liste die Geohashes Ihrer Koordinaten aus Schritt 3 hinzu.
6. Dann müssen Sie eine Reihe von Geohash-Werten für die Suche erstellen, die diese 9 Bereiche abdecken. Die Werte aus Schritt 5 sind Ihr unteres Bereichslimit. Wenn Sie zu jedem Wert 1 hinzufügen, erhalten Sie Ihr oberes Bereichslimit. Sie sollten also ein Array von 9 Bereichen mit jeweils einer unteren Grenze und einer oberen Geohash-Grenze (insgesamt 18 Geohashes) haben. Diese Geohashes befinden sich noch in der niedrigeren Auflösung von Schritt 2.
7. Dann konvertieren Sie alle 18 dieser Geohashes in die Bittiefe / Auflösung, in der Sie alle Ihre Geohashes in Ihrer Datenbank gespeichert haben. Im Allgemeinen tun Sie dies, indem Sie sie auf die gewünschte Bittiefe verschieben.
8. Jetzt können Sie eine Bereichsabfrage für Punkte innerhalb dieser 9 Bereiche durchführen, und Sie erhalten alle Punkte ungefähr in der Entfernung Ihres ursprünglichen Punkts. Es wird keine Überlappung geben, sodass Sie keine Schnittmengen, sondern nur reine Bereichsabfragen, sehr schnell ausführen müssen. (dh in redis: ZRANGEBYSCORE zsetname lowerLimit upperLimit, über die in diesem Schritt erzeugten 9 Bereiche)

Sie können dies weiter optimieren (in Bezug auf die Geschwindigkeit), indem Sie:

1. Das Aufnehmen dieser 9 reicht von Schritt 6 bis zum Finden, wo sie ineinander führen. Normalerweise können Sie 9 separate Bereiche auf 4 oder 5 reduzieren, je nachdem, wo sich Ihre Koordinate befindet. Dies kann Ihre Abfragezeit um die Hälfte reduzieren.
2. Sobald Sie Ihre endgültigen Bereiche haben, sollten Sie sie zur Wiederverwendung bereithalten. Die Berechnung dieser Bereiche kann den größten Teil der Verarbeitungszeit in Anspruch nehmen. Wenn sich Ihre ursprüngliche Koordinate also nicht wesentlich ändert, Sie jedoch dieselbe Entfernungsabfrage erneut durchführen müssen, sollten Sie diese bereithalten, anstatt sie jedes Mal zu berechnen.
3. Wenn Sie Redis verwenden, versuchen Sie, die Abfragen in einer MULTI / EXEC-Datei zu kombinieren, damit sie für eine etwas bessere Leistung per Pipeline übertragen werden.
4. Der BESTE Teil: Sie können die Schritte 2 bis 7 auf die Clients verteilen, anstatt diese Berechnung an einem Ort durchführen zu lassen. Dadurch wird die CPU-Auslastung in Situationen, in denen Millionen von Anforderungen eingehen würden, erheblich reduziert.

Sie können die Genauigkeit weiter verbessern, indem Sie für die zurückgegebenen Ergebnisse eine Kreisentfernungs- / Haversinusfunktion verwenden, wenn Sie viel Wert auf Präzision legen.

Hier ist eine ähnliche Technik, bei der normale Base32-Geohashes und eine SQL-Abfrage anstelle von Redis verwendet werden: https://github.com/davetroy/geohash-js

Ich möchte nicht mein eigenes Ding einstecken, aber ich habe ein Modul für nodejs & redis geschrieben, das die Implementierung wirklich einfach macht. Schauen Sie sich den Code an, wenn Sie möchten: https://github.com/arjunmehta/node-georedis

Die Frage kann auf verschiedene Arten gelesen werden. Ich interpretiere es so, dass Sie eine große Anzahl von Punkten haben und Sie beabsichtigen, diese wiederholt mit willkürlichen Punkten abzutasten, die als Koordinatenpaare angegeben sind, und die n nächstgelegenen Punkte zur Sonde zu erhalten, wobei n vorher festgelegt wurde. (Wenn n variieren soll, können Sie im Prinzip für jedes mögliche n eine Datenstruktur einrichten und diese mit jeder Sonde in O (1) -Zeit auswählen. Dies kann eine sehr lange Einrichtungszeit in Anspruch nehmen und viel RAM erfordern, aber wir werden aufgefordert, solche Bedenken zu ignorieren.)

Erstellen Sie das Order-n-Voronoi-Diagramm aller Punkte. Dadurch wird die Ebene in verbundene Bereiche unterteilt, von denen jeder die gleichen n Nachbarn hat. Dies reduziert die Situation auf das Punkt-in-Polygon-Problem, das viele effiziente Lösungen bietet.

Bei Verwendung einer Vektordatenstruktur für das Voronoi-Diagramm dauert die Punkt-in-Polygon-Suche O (log (n)). Aus praktischen Gründen können Sie dieses O (1) mit einem extrem kleinen impliziten Koeffizienten erstellen, indem Sie einfach eine Rasterversion des Diagramms erstellen. Die Werte der Zellen im Raster sind entweder (i) ein Zeiger auf eine Liste der n nächsten Punkte oder (ii) ein Hinweis darauf, dass diese Zelle zwei oder mehr Bereiche im Diagramm überspannt. Der Test für einen beliebigen Punkt bei (x, y) lautet:

Fetch the cell value for (x,y).
If the value is a list of points, return it.
Else apply a vector point-in-polygon algorithm to (x,y).

Um eine O (1) -Leistung zu erzielen, muss das Rasternetz ausreichend fein sein, damit relativ wenige Prüfpunkte in Zellen fallen, die mehrere Voronoi-Regionen überspannen. Dies kann immer mit einem potenziell hohen Speicheraufwand für die Gitter erreicht werden.

Ich benutze dafür Geohashes. Der Grund dafür ist, dass ich mithilfe eines Informationssystems im Pyramidenstil Näherungssuchen implementieren musste. Dabei waren Geohashes mit einer Genauigkeit von 8 die Basis und bildeten neue Summen für Geohashes mit einer Genauigkeit von 7 und so weiter . Diese Summen waren Fläche, Arten von Bodendecker usw. Es war eine sehr ausgefallene Art, einige sehr ausgefallene Sachen zu machen.

Geohashes der 8. Ebene enthalten also Informationen wie:

Typ: Grasfläche: 1,23

und 7., 6. .. etc .. würde Informationen enthalten wie:

grass_types: 123 acres: 6502

Dies wurde immer mit der geringsten Präzision aufgebaut. Dies ermöglichte es mir, alle möglichen lustigen Statistiken sehr schnell zu erstellen. Außerdem konnte ich mit GeoJSON jeder Geohash-Referenz eine Geometrie-Referenz zuweisen.

Ich konnte mehrere Funktionen schreiben, um die größten Geohashes zu finden, aus denen sich mein aktuelles Ansichtsfenster zusammensetzt, und diese dann verwenden, um Geohashes mit der zweitgrößten Genauigkeit im Ansichtsfenster zu finden. Dies könnte leicht auf indizierte Bereichsabfragen ausgedehnt werden, bei denen ich nach einem Minimum von '86ssaaaa' und einem Maximum von '86sszzzz' für die von mir gewünschte Genauigkeit frage.

Ich mache das mit MongoDB.

Aktualisierung für 2018 und einige mathematische Fundamente oder historische Herkunft von Geohash:

• Die Inspiration für Geohash war die einfache Interlave von Binärziffern , vielleicht eine Optimierung von naiven Algorithmen, die Dezimalziffern wie die von C-Quadraten verschachtelten .

• die binäre Interlacing führte zu einer Z-Order-Kurve Index Strategie natürlich Geohash Erfinder nicht gestartet „für die beste fraktale Kurve suchen“ ... Aber curiosally dieses Design - Optimierung, eine bessere fraktale Kurve ist möglich (!).

Verwenden Sie die S2 Geometry Library

Der S2-Geometrie-Ansatz ist besser als Geohash, da er die kugelförmige Topologie des Globus (einen Würfel) verwendet, eine optionale Projektion verwendet (damit alle Zellen nahezu dieselbe Form und nahezu dieselbe Fläche haben) und weil die Indizierung mit der Hilbert-Kurve besser ist als Z- Bestellkurve :

... wir können es besser machen ... Die Diskontinuität beim Übergang vom rechten oberen zum linken unteren Quad führt dazu, dass wir einige Bereiche aufteilen müssen, die wir sonst zusammenhängend machen könnten. (...) Unstetigkeiten (...) blog.notdot.net/2009 zur räumlichen Indizierung mit Quadtrees und Hilbert Curves können wir vollständig beseitigen

Jetzt ist es eine kostenlose und effiziente Bibliothek, siehe https://s2geometry.io

PS: Es gibt auch (gute) nicht offizielle vereinfachte Versionen wie NodeJSs2-geometry und viele "Spielplätze", Add-Ins und Demos wie s2.sidewalklabs.com .

Ich würde empfehlen, die GEORADIUS-Abfrage in redis zu verwenden.

Verschieben Sie die Daten, die von der am besten geeigneten Geohash-Ebene stammen, mithilfe des GEOADD-Aufrufs.

Schauen Sie sich auch diese an -> ProximityHash .

ProximityHash generiert eine Reihe von Geohashes, die unter Berücksichtigung der Mittelpunktskoordinaten und des Radius eine kreisförmige Fläche abdecken. Es gibt auch eine zusätzliche Option für die Verwendung von GeoRaptor, mit der die beste Kombination von Geohashes auf verschiedenen Ebenen erstellt wird, um den Kreis darzustellen. Beginnen Sie auf der höchsten Ebene und iterieren Sie, bis die optimale Mischung hergestellt ist. Die Genauigkeit des Ergebnisses bleibt mit der des Start-Geohash-Levels identisch, die Datengröße wird jedoch erheblich verringert, wodurch Geschwindigkeit und Leistung verbessert werden.