Sono interessato alla buona letteratura sugli indici spaziali. Quali sono in uso, i confronti tra loro in termini di velocità, requisiti di spazio, prestazioni spaziali query quando li utilizza ecc.Buoni libri/articoli sugli indici spaziali
Ho usato un tipo di QuadTree cresciuto in proprio per l'indicizzazione spaziale (ben prima che imparassi la parola "quadtree" "). Per tipi ordinari di dati spaziali (mi occupo dei dati delle mappe stradali), sono veloci da creare e veloci da interrogare, ma analizzano troppi nodi foglia durante le query. In particolare, con dimensioni di nodo ragionevoli (50-100), il mio quadripeso tendeva a produrre circa 300 risultati per una query puntuale, vale a dire 3-6 nodi fogliari (campo molto approssimativo, i risultati sono molto variabili)
Al giorno d'oggi, il mio la struttura dati preferita è l'albero R *. Ho scritto e testato personalmente una implementazione che ha ottenuto ottimi risultati. Il mio codice per la costruzione di un albero R * è molto lento rispetto al mio codice QuadTree, ma le caselle di delimitazione sui nodi foglia sono finite molto bene organizzate; almeno la metà dello spazio di query ha una risposta da un solo nodo foglia (cioè se si esegue una query a punti casuali, c'è una buona probabilità che venga restituito solo un nodo a foglia singola) e qualcosa come il 90% dello spazio è coperto da due nodi o meno. Quindi con una dimensione del nodo di 80 elementi, in genere ottengo 80 o 160 risultati da una query puntuale, con la media più vicina a 160 (poiché alcune query restituiscono 3-5 nodi). Ciò è vero anche nelle aree urbane densamente popolate della mappa.
Lo so perché ho scritto un visualizzatore per il mio albero R * e gli oggetti grafici al suo interno, e l'ho testato su un grande set di dati (600.000 segmenti stradali). Funziona ancora meglio sui dati dei punti (e altri dati in cui i bounding box raramente si sovrappongono). Se implementi un albero R * ti invito a visualizzare i risultati, perché quando ho scritto il mio aveva più bug che abbassavano l'efficienza dell'albero (senza intaccare la correttezza), e sono stato in grado di modificare alcuni dei processi decisionali per ottenere risultati migliori Assicurati di testare su un set di dati di grandi dimensioni, in quanto rivelerà problemi che un piccolo set di dati non ha. Può aiutare a ridurre il fan-out (dimensione del nodo) dell'albero per il test, per vedere quanto l'albero funzioni quando è profondo più livelli.
Sarei felice di darti il codice sorgente tranne che avrei bisogno del permesso del mio datore di lavoro. Sai com'è. Nella mia implementazione sono supportato il reinserimento forzato, ma la penalità di inserimento di PickSplit e è stata ottimizzata.
Il documento originale, The R* tree: An Efficient and Robust Access Method for Points and Rectangles, manca di punti per qualche motivo (nessun punto e nessun punto sulle "i"). Inoltre, la loro terminologia è un po 'strana, ad es. quando dicono "margine", ciò che intendono è "perimetro".
L'albero R * è una buona scelta se è necessaria una struttura dati che può essere modificata. Se non è necessario modificare l'albero dopo averlo creato, considerare bulk loading algorithms. Se hai solo bisogno di modificare l'albero una piccola quantità dopo il caricamento in serie, gli algoritmi R-tree ordinari saranno abbastanza buoni. Si noti che i dati R * -tree e R-tree sono strutturalmente identici; solo gli algoritmi per l'inserimento (e forse la cancellazione? mi dimentico) sono diversi. R-tree è la struttura dati originale del 1984; ecco un collegamento allo R-tree paper.
Il kd-tree sembra efficiente e non troppo difficile da implementare, ma può essere utilizzato solo per i dati punto.
Tra l'altro, la ragione mi concentro su nodi foglia così tanto è che
Ho sviluppato un algoritmo per la ricerca veloce basata su quadrante e l'ho pubblicato su ddj.com un paio di anni fa. Forse è interessante per voi:
accelerata Ricerca Per la linea più vicina http://drdobbs.com/windows/198900559