Ottimizzazione delle query, miglioramento dei tempi di esecuzione e applicazioni di data science geospaziale
Nello svolgere il lavoro di data science geospaziale, è molto importante pensare a ottimizzare il codice che stai scrivendo. Come è possibile aggregare o unire più rapidamente set di dati con centinaia di milioni di righe? È qui che entrano in gioco concetti come gli indici spaziali. In questo post parlerò di come viene implementato un indice spaziale, quali sono i suoi vantaggi e limiti e darò un’occhiata alla libreria di indicizzazione H3 open source di Uber per alcune interessanti scienze dei dati spaziali. applicazioni. Iniziamo!
Un indice regolare è il tipo di cosa che potresti trovare alla fine di un libro: un elenco di parole e la posizione in cui sono apparse nel testo. Questo ti aiuta a cercare rapidamente qualsiasi riferimento a una parola che ti interessa all’interno di un determinato testo. Senza questo pratico strumento, dovresti sfogliare manualmente ogni pagina del tuo libro, cercando quella menzione di cui vorresti leggere.
Nei database moderni, anche la questione delle interrogazioni e delle ricerche è molto pertinente. L’indicizzazione spesso rende la ricerca dei dati più rapida rispetto al filtraggio ed è possibile creare indici basati su una colonna di interesse. Per i dati geospaziali in particolare, gli ingegneri spesso devono considerare operazioni come “intersezione” o “è vicino a”. Come possiamo creare un indice spaziale affinché queste operazioni siano il più veloci possibile? Innanzitutto, diamo un’occhiata ad alcuni di questi dati geospaziali:
Diciamo che vogliamo eseguire una query per determinare se queste due forme si intersecano. Per costruzione, i database spaziali creano il loro indice da un riquadro di delimitazione che contiene la geometria:
Per rispondere se queste due caratteristiche si intersecano, il database confronterà se i due riquadri di delimitazione hanno un’area in comune. Come puoi vedere, questo può portare rapidamente a falsi positivi. Per risolvere questo problema, i database spaziali come PostGIS in genere suddividono questi grandi riquadri di delimitazione in riquadri sempre più piccoli:
Queste partizioni sono archiviate in R-tree. Gli R-tree sono una struttura dati gerarchica: tengono traccia del grande riquadro di delimitazione “genitore”, dei suoi figli, dei figli dei suoi figli e così via. Il riquadro di delimitazione di ogni genitore contiene i riquadri di delimitazione dei suoi figli:
L’operazione “intersect” è una delle operazioni chiave che beneficia di questa struttura. Durante l’interrogazione di un’intersezione, il database esamina questo albero chiedendo “il riquadro di delimitazione corrente interseca l’elemento di interesse?”. Se sì, esamina i figli di quel riquadro di delimitazione e pone la stessa domanda. Così facendo, è in grado di attraversare velocemente l’albero, saltando i rami che non hanno intersezione e migliorando così le prestazioni della query. Alla fine, restituisce la geometria intersecante come desiderato.
Diamo ora uno sguardo concreto a come appare l’utilizzo di una normale procedura per righe rispetto a un indice spaziale. Utilizzerò 2 set di dati che rappresentano i tratti di censimento di New York e le strutture cittadine (entrambi concessi in licenza tramite Open Data e disponibili Qui E Qui). Per prima cosa, proviamo l’operazione di “intersezione” in GeoPandas su una delle geometrie del Census Tract. ‘Intersezione’ in GeoPanda è una funzione per riga che controlla ciascuna riga della colonna di interesse rispetto alla nostra geometria e controlla se si intersecano o meno.
GeoPandas offre anche un’operazione di indice spaziale che utilizza R-tree e ci consente anche di eseguire intersezioni. Ecco un confronto in fase di esecuzione dei due metodi su 100 esecuzioni dell’operazione di intersezione (nota: poiché la funzione di intersezione predefinita è lenta, ho selezionato solo circa 100 geometrie dal set di dati originale):
Come puoi vedere, l’approccio dell’indice spaziale ha offerto prestazioni molto migliori rispetto al metodo dell’intersezione vanilla. Infatti, ecco gli intervalli di confidenza al 95% per i tempi di esecuzione di ciascuno:
