C'è un modo per aggiungere punti all'implementazione dell'albero KD in Scipy

Question

Ho un set di punti per il quale voglio costruire KD Tree. Dopo un po 'di tempo voglio aggiungere qualche altro punto a questo KDTree periodicamente. C'è un modo per farlo nell'implementazione scipy

Answer 1

Il problema con k-d-trees è che sono non progettato per gli aggiornamenti.

Mentre è possibile inserire oggetti con facilità (se si utilizza una rappresentazione basata su puntatore, che richiede molta più memoria di un albero basato su array) e si eliminano con trucchi come i messaggi tombstone, eseguendo tali modifiche sarà degenerare prestazioni dell'albero.

Non sono a conoscenza di un buon metodo per riequilibrare in modo incrementale un albero K-D. Per gli alberi 1-dimensionale hai alberi rosso-neri, alberi B, alberi B *, alberi B + e cose simili. Questi ovviamente non funzionano con gli alberi k-d a causa degli assi rotanti e quindi della diversa classificazione. Quindi, alla fine, con una k-d-tree, potrebbe essere meglio raccogliere solo le modifiche e di tanto in tanto fare una ricostruzione completa dell'albero . Quindi almeno questa parte dell'albero sarà abbastanza buona.

Tuttavia, esiste una struttura simile (che nei miei esperimenti sovrasta spesso il k-d-tree!): L'R * -tree. Invece di eseguire divisioni binarie, usa rettangoli di selezione per raccogliere oggetti, e si è pensato molto a rendere l'albero una struttura dati dinamica. Questo è anche il punto in cui il R * -tree si comporta molto meglio dell'albero R: ha una divisione molto più intelligente per la ricerca in kNN, ed esegue un riequilibrio incrementale per migliorare la sua struttura.