Interrogazioni spaziali su AWS SimpleDB

Question

Vorrei sapere che cosa le persone suggeriscono come modi efficienti di eseguire una query spaziale in un SimpleDB di Amazon Web Services?

Per query spaziale intendo la ricerca di oggetti in un dato raggio di latitudine e longitudine.

Answer 1

SimpleDB attualmente non offre alcuna funzione di ricerca spaziale integrata, ma ciò non significa che non possa essere eseguita. Esistono diversi metodi per implementare ricerche geospaziali in database non geospaziali come SimpleDB e tutti ruotano intorno all'idea di utilizzare il database per recuperare una prima selezione approssimativa basata su un riquadro di delimitazione geospaziale e quindi filtrare i dati restituiti nell'applicazione utilizzando algoritmi più accurati come lo Haversine formula.

È potrebbe negozio di latitudine e longitudine come (zero-imbottito e normalizzato) attributi numerici e quindi eseguire una query di gamma doppia (lat >= minLat and lat <= maxLat and lon >= minLat and lon <= maxLat), ma dal momento che nessuno dei due theese predicati sono selettivi (ogni predicato corrisponde a un sacco di oggetti) non è l'ideale (vedi Tuning Queries).

Un modo migliore sarebbe utilizzare GeoHashes.

Geohashes offrono immobili come precisione arbitraria, prefissi simili per le posizioni vicine, e la possibilità di rimuovere gradualmente caratteri dalla fine del codice per ridurne le dimensioni (e gradualmente perdere precisione).

Come esempio pratico, il Geohash 6gkzwgjzn820 decodifica al coordina la -25,382708 e -49,265506, mentre il Geohash 6gkzwgjz sarà decodifica a -25,383 e -49,266, e se prendiamo una posizione simile a stessa regione, come -25.427 e -49.315, possiamo vedere che è codificato come come 6gkzmg1w (si noti il ​​prefisso simile).

Da http://geohash.org/site/tips.html

Con le vostre posizioni elemento come GeoHashes è possibile utilizzare l'operatore like per la ricerca di un rettangolo di selezione (where GeoHash like '6gkzmg1w%'), ma dal momento che l'operatore like è costoso (Comparison Operators) un modo migliore sarebbe quello di denormalizzare i dati memorizzando ciascun livello di prefisso GeoHash (quanti dipendono dalla precisione di ricerca richiesta) come attributo separato (GeoHash6 GeoHash8 ecc.) e quindi utilizzare un semplice predicato di uguaglianza (where Geohash8 = '6gkzmg1w').

Ora sul lato negativo di GeoHashes. Dal momento che non è possibile ipotizzare che un GeoHash sia centrato all'interno della casella di ricerca, è necessario cercare anche tutti i prefissi vicini. Il processo è ottimamente descritto da geohash-js

Geohash ha anche la proprietà che il numero di cifre diminuisce (da destra), la precisione degrada. Questa proprietà può essere utilizzata per effettuare ricerche nel riquadro di selezione , poiché i punti vicini tra loro condivideranno i prefissi di Geohash simili.

Tuttavia, dato che un determinato punto può apparire ai margini di un dato Geohash riquadro di delimitazione, è necessario generare un elenco di Geohash valori al fine di effettuare una vera e propria ricerca di prossimità intorno a un punto. Poiché l'algoritmo Geohash utilizza un sistema di numerazione di base 32, è possibile ricavare i valori Geohash circostanti qualsiasi altro dato valore Geohash utilizzando una semplice tabella di ricerca.

Così, per esempio, 1600 Pennsylvania Avenue, Washington DC delibera di: 38,897, -77,036

Usando l'algoritmo geohash, questa latitudine e longitudine viene convertito a: dqcjqcp84c6e

Un semplice rettangolo di selezione attorno a questo punto può essere descritta da troncando questo geohash a: dqcjqc

Tuttavia, 'dqcjqcp84c6e' non è centrata all'interno 'dqcjqc', e la ricerca all'interno 'dqcjqc' può perdere alcune targe desiderato ts.

Così, invece, siamo in grado di utilizzare le proprietà matematiche della Geohash per calcolare rapidamente i vicini di 'dqcjqc'; troviamo che essi sono: 'dqcjqf', 'dqcjqb', 'dqcjr1', 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8'

Questo ci dà un rettangolo di selezione intorno ' dqcjqcp84c6e 'circa 2km x 1.5km e consente una ricerca nel database su solo 9 tasti: SELECT * FROM table WHERE LEFT (geohash, 6) IN (' dqcjqc ', ' dqcjqf ',' dqcjqb ',' dqcjr1 ', 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8');

Tradotto in una query SimpleDB che sarebbe where GeoHash6 in('dqcjqc', 'dqcjqf', 'dqcjqb', 'dqcjr1', 'dqcjq9', 'dqcjqd', 'dqcjr4', 'dqcjr0', 'dqcjq8') e poi ti fai del tuo filtraggio Haversine sui risultati al fine di ottenere solo gli elementi che è all'interno del vostro raggio di ricerca.

Answer 2

Ho intenzione di lasciarlo qui perché potrebbe aiutarti!

14 anni fa abbiamo cercato di fare una tabella di ricerca geo di posizioni all'interno di un raggio. Non c'erano ovviamente indici geospaziali o qualcosa del genere. C'era letteralmente solo SQL standard e Oracle ... comunque, abbiamo finito per convertire tutto il lat/lng in chilometri da un campo piano fisso. In sostanza, quali sono gli indici geospaziali in questi giorni.

Per spiegare che cosa fa esattamente, trasforma il mondo in una superficie piana e con un po 'di trucchi SQL è possibile selezionare anche per raggio, si ottiene anche la distanza dai due punti che si sta selezionando. Poiché sono anche interi interi non elaborati, le query sono velocissime.

Ecco un semplice esempio in PHP e un guardando molto complesso, ma abbastanza facile una volta capito che query SQL:

https://gist.github.com/tobsn/899413