Welche Art von Datenstruktur könnte für eine effiziente Nearest-Neighbor-Suche in einer großen Menge von Geo-Koordinaten verwendet werden? Bei "normalen" räumlichen Indexstrukturen wie R-Trees, die planare Koordinaten annehmen, sehe ich zwei Probleme (Gibt es andere, die ich übersehen habe?):
Wie können diese Faktoren berücksichtigt werden? Ich denke, der zweite könnte durch die Koordinatenumwandlung kompensiert werden. Kann ein R-Tree modifiziert werden, um den Umlauf zu berücksichtigen? Oder gibt es spezielle geo-räumliche Indexstrukturen?
Werfen Sie einen Blick auf Geohash .
Um den Wraparound zu kompensieren, verwenden Sie einfach nicht einen, sondern drei orthogonale R-Bäume, so dass kein Punkt auf der Erdoberfläche existiert, so dass alle drei Bäume an diesem Punkt einen Umbruch haben. Dann sind zwei Punkte nahe, wenn sie sich in der Nähe von mindestens einem dieser Bäume befinden.
Könnten Sie einen Locality-Sensitive Hashing (LSH) -Algorithmus in 3 Dimensionen verwenden? Das würde Ihnen schnell eine ungefähre Nachbargruppe geben, die Sie dann durch Berechnung der Großkreisabstände überprüfen könnten.
Hier ist ein Papier , das einen Algorithmus für effiziente LSH auf der Oberfläche einer Einheit beschreibt d -dimensionale Hypersphäre. Vermutlich funktioniert es für d = 3.
Tags und Links indexing geospatial data-structures