Albero Kd: i dati sono memorizzati solo nelle foglie e conservati nelle foglie e nei nodi

Question

Sto cercando di implementare un albero Kd per eseguire il prossimo più prossimo e approssimare la ricerca vicino più vicino in C++. Finora mi sono imbattuto in 2 versioni dell'albero di base più semplice.

1. L'uno, in cui i dati vengono memorizzati nei nodi e nelle foglie, come ad esempio here
2. L'uno, in cui i dati vengono memorizzati solo nelle foglie, come ad esempio here

Essi sembrano essere fondamentalmente lo stesso, con le stesse proprietà asintotiche.

La mia domanda è: ci sono alcuni motivi per cui scegliere uno rispetto all'altro?

ho pensato due ragioni finora:

1. L'albero che memorizza i dati nei nodi troppo è meno profonda di 1 livello.
2. L'albero che memorizza i dati solo in foglie ha più facili da implementare delete data funzione

Ci sono alcune altre ragioni che dovrebbero prendere in considerazione prima di decidere quale fare?

Answer 1

È possibile solo contrassegnare i nodi come cancellati e posticipare eventuali modifiche strutturali alla successiva ricostruzione dell'albero. Gli alberi k-d si degradano nel tempo, quindi dovrai eseguire frequenti ricostruzioni degli alberi. Gli alberi k-d sono ottimi per i set di dati a bassa dimensionalità che non cambiano, o dove puoi facilmente permetterti di ricostruire un albero (approssimativo) ottimale.

Per quanto riguarda l'implementazione dell'albero, consiglio di utilizzare una struttura minimalista. Io di solito uso i nodi non. Io uso una matrice di riferimenti a oggetti di dati. L'asse è definito dalla profondità di ricerca corrente, non è necessario memorizzarlo da nessuna parte. I vicini sinistro e destro sono dati dall'albero di ricerca binario dell'array. (Altrimenti, basta aggiungere un array di byte, metà della dimensione del set di dati, per memorizzare gli assi utilizzati). Il caricamento dell'albero viene eseguito da un QuickSort specializzato. In teoria è O(n^2) nel peggiore dei casi, ma con una buona euristica come la mediana di 5 è possibile ottenere O(n log n) in modo abbastanza affidabile e con un sovraccarico costante minimo.

Sebbene non contenga tanto per C/C++, in molti altri linguaggi pagherai un prezzo abbastanza elevato per la gestione di molti oggetti. A type*[] è la struttura dati più economica che si possa trovare e, in particolare, non richiede un notevole sforzo di gestione. Per contrassegnare un elemento come eliminato, è possibile eseguire null e cercare entrambi i lati quando si incontra uno null. Per gli inserimenti, prima li raccoglievo in un buffer. E quando il contatore delle modifiche raggiunge una soglia, ricostruire.

E questo è il punto principale: se il tuo albero è davvero economico da ricostruire (a buon mercato come ricorrere a un array quasi preordinato!), Allora non danneggia la ricostruzione frequente dell'albero. La scansione lineare su una breve "lista di inserimento" è molto adatta alla cache della CPU. Anche saltare null s è molto economico.

Se si desidera una struttura più dinamica, si consiglia di guardare R * -trees.Sono in realtà desiderati di bilanciare inserimenti e cancellazioni e organizzare i dati in una struttura a blocchi orientata al disco. Ma anche per gli alberi R, ci sono stati rapporti sul fatto che mantenere un buffer di inserimento, ecc., Per rinviare le modifiche strutturali, migliora le prestazioni. Anche il caricamento di massa in molte situazioni aiuta molto!