Ich würde gerne wissen, was die Leute als effiziente Möglichkeiten für eine räumliche Abfrage in einer Amazon Web Services SimpleDB vorschlagen?Räumliche Abfragen in AWS SimpleDB
Mit räumlicher Abfrage meine ich Objekte in einem bestimmten Radius einer Breite und Länge zu finden.
SimpleDB bietet derzeit keine integrierten räumlichen Suchoperationen, aber das bedeutet nicht, dass dies nicht möglich ist. Es gibt mehrere Methoden zur Implementierung von Geospatial-Suchanfragen in nicht geospatial-sensitiven Datenbanken wie SimpleDB. Alle basieren auf der Idee, mithilfe der Datenbank eine grobe erste Auswahl basierend auf einer raumbezogenen Bounding-Box zu erhalten und dann die zurückgegebenen Daten in Ihrer Anwendung zu filtern genauere Algorithmen wie die Haversine formula.
Sie konnte speichert die Breite und Länge als (mit Nullen aufgefüllt und normalisiert) numerische Attribute und dann eine Doppelbereichsabfrage (lat >= minLat and lat <= maxLat and lon >= minLat and lon <= maxLat) durchführen, aber da selektive weder ond Prädikate sind (jedes Prädikat eine Menge von Elementen übereinstimmt) es ist nicht ideal (siehe Tuning Queries).
Ein besserer Weg wäre die Verwendung GeoHashes.
Geohashes bieten Eigenschaften wie beliebige Genauigkeit, Ähnliche Präfixe für in der Nähe Positionen, und die Möglichkeit, nach und nach Zeichen aus dem Ende des Codes zu entfernen seine Größe (und allmählich verlieren Präzision) zu reduzieren.
Als ein praktisches Beispiel, das Geohash 6gkzwgjzn820 dekodiert, um die Koordinaten -25,382708 und -49,265506, während der Geohash 6gkzwgjz wird Decodierung -25,383 -49,266 und, und wenn wir eine ähnliche Position in die gleiche Region, wie -25.427 und -49.315, können wir sehen, dass es codiert als 6gkzmg1w (beachten Sie die ähnliche Präfix).
Von http://geohash.org/site/tips.html
mit Ihrem Artikel Positionen als GeoHashes könnten Sie den like Operator für einen Begrenzungsrahmen (where GeoHash like '6gkzmg1w%') suchen, aber da die like Betreiber teuer (Comparison Operators) ein besserer Weg wäre denormalize Die Daten werden durch Speicherung jedes GeoHash-Präfix-Levels (wie viele davon von der benötigten Suchpräzision abhängen) als separates Attribut (GeoHash6 GeoHash8 usw.) und dann Verwendung eines einfachen Gleichheitsprädikats (where Geohash8 = '6gkzmg1w').
Jetzt auf den Nachteil von GeoHashes. Da Sie nicht davon ausgehen können, dass ein GeoHash in Ihrem Suchfeld zentriert ist, müssen Sie auch alle benachbarten Präfixe durchsuchen. Das Verfahren hervorragend durch geohash-js
Geohash auch die Eigenschaft beschrieben wird, haben, die als die Anzahl der Stellen verringert (von rechts), die Genauigkeit verschlechtert. Diese Eigenschaft kann verwendet werden, um Bounding-Box-Suchen zu tun, da Punkte in der Nähe von ähnliche Geohash-Präfixe teilen.
Da jedoch ein gegebener Punkt an der Kante einer gegebenen Geohash Bounding Box erscheinen kann, ist es notwendig, eine Liste von Geohash Werten zu erzeugen, um eine der tatsächliche Umgebungs-Suche um einen Punkt durchzuführen. Da der Geohash-Algorithmus ein Basis-32-Nummerierungssystem verwendet, ist es möglich, die Geohash-Werte, die einen anderen gegebenen Geohash-Wert umgeben, mithilfe einer einfachen Nachschlagetabelle abzuleiten.
So zum Beispiel, 1600 Pennsylvania Avenue, löst Washington DC: 38,897, -77,036
den geohash Algorithmus verwenden, diese geografische Breite und Länge zu umgewandelt wird: dqcjqcp84c6e
Eine einfache Zeichen-Box um diesen Punkt durch Kürzen dieses geohash zu beschreiben könnte: dqcjqc
jedoch ‚dqcjqcp84c6e‘ ist nicht in ‚dqcjqc‘ zentriert und innerhalb ‚dqcjqc‘ Suche kann einige gewünschte targe verpassen ts.
Also können wir stattdessen die mathematischen Eigenschaften des Geohash zu schnell die Nachbarn von 'dqcjqc' berechnen; wir finden, dass sie sind: 'dqcjqf', 'dqcjqb', 'dqcjr1', 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8'
Diese uns einen Begrenzungsrahmen gibt um ' dqcjqcp84c6e 'ungefähr 2km x 1.5km und ermöglicht eine Datenbanksuche mit nur 9 Schlüsseln: SELECT * FROM Tabelle WHERE LINKS (geohash, 6) IN (' dqcjqc ', ' dqcjqf ',' dqcjqb ',' dqcjr1 ', "dqcjq9", "dqcjqd", "dqcjr4", "dqcjr0", "dqcjq8");
zu einer SimpleDB Abfrage übersetzt, die where GeoHash6 in('dqcjqc', 'dqcjqf', 'dqcjqb', 'dqcjr1', 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8') sein würde und dann werden Sie über die Ergebnisse, um Ihre Haversine Filterung nur tun, um die Elemente, die in deinen Suchradius ist.
Ich werde das hier lassen, weil es Ihnen helfen könnte!
Vor 14 Jahren haben wir versucht, eine Geo-Lookup-Tabelle von Orten innerhalb eines Radius zu erstellen. Es gab offensichtlich keine Geodatenindizes oder ähnliches. Es gab buchstäblich nur Standard-SQL und Oracle ... trotzdem wandelten wir alle lat/lng in Kilometer von einem festen Flugzeugfeld um. Im Wesentlichen was Geospatial-Indizes in diesen Tagen tun.
Um zu erklären, was genau es macht, verwandelt es die Welt in eine flache Oberfläche und mit ein bisschen SQL-Tricks können Sie sogar nach Radius wählen, Sie erhalten sogar die Entfernung von den zwei Punkten, die Sie auswählen. Da es auch ganze Zahlen sind, sind die Abfragen blitzschnell.
Hier ist ein einfaches Beispiel in PHP und eine sehr komplexe suchen, aber ziemlich einfach, wenn Sie es SQL-Abfrage verstehen:
Ausgezeichnete Antwort, danke für die Diskussion über Geohashes – user293895