Q: k-d-tree: funzionamento, struttura.
A:
Il k-d-tree è una struttura di indicizzazione ad albero pensata per la memoria principale, quindi non adatta alla memoria secondaria in quanto non bilanciata e non paginata.
La sigla k-d, sta per [i]k-dimensionality[/b]. È quindi una struttura di indicizzazione per dimensioni maggiori di 1.
Per dimensione, intendiamo un attributo che può variare in un range di valori.
La combinazione di più attributi determina la dimensione maggiore di uno.
Questo tipo di albero utilizza il concetto di partizionamento in intervalli degli assi cartesiani per permettere di indicizzare i valori.
Il k-d-tree è un albero binario di ricerca, in cui ogni livello è etichettato (ciclicamente) con una delle n coordinate ed in ogni nodo è presente un separatore dato dal valore mediano dell'intervallo che si sta partizionando.
La seguente immagine aiuterà nella spiegazione:
In questo caso, vogliamo indicizzare tramite k-d-tree l'insieme di punti mostrato in figura.
Per ogni dimensione (ne abbiamo 2 in questo caso), si inizia suddividendo l'asse in 2 parti, utilizzando come punto per la suddivisione il valore mediano.
In questo modo abbiamo suddiviso il piano in due semipiani distinti. Nella parte di sinistra troveremo i valori minori o uguali al valore mediano, nella parte destra quelli maggiori.
Si passa all'altra coordinata, si effettua la stessa operazione per ogni semipiano venutosi a creare.
Così via fino a che la suddivisione non contiene alcun punto, in tal caso la generazione dell'albero è terminata. Riconducendosi a questa suddivisione:
È quindi possibile effettuare ricerche all'interno di questo albero sfruttando l'ordinamento delle singole coordinate, attraversandolo dalla radice fino alla foglia desiderata, la quale potrà contenere il punto cercato.
Ovviamente il tipo di ricerca varierà a seconda del tipo di query effettuata, in quanto per una window query è necessario trovare valori in un intervallo, quindi sarà necessario scorrere l'albero anche all'indietro (backtraking) se l'intervallo della windows query contiene più regioni.
Quando si deve inserire un nuovo elemento si cerca la foglia che deve contenerlo e se la foglia è piena (overflow) ovviene uno split verso il basso come accade in un albero binario (e non come accade nel B(+|-)tree, dove lo split avviene verso l'alto).
L'albero non è bilanciato e periodicamente richiede una riorganizzazione.
Le cancellazioni sono molto complicate, soprattutto se si vogliono effettuare merge delle foglie in underflow.
Come precedentemente detto, questo albero utilizza il partizionamento in intervalli degli assi cartesiani per poter permettere l'indicizzazione dei valori.
La tecnica mostrata precedentemente usa il partizionamento tramite valore mediano, ma non è la sola possibile.
Esistono diverse varianti per gestire in maniera diversa i separatori, come ad esempio il BSP tree che utilizza degli iperpiani non paralleli agli assi (cosa che con il metodo del valore mediano invece si ha), oppure il VAMsplit kd-tree che sceglie la coordinata migliore di split per ogni nodo come quella avente maggior varianza.
A:
Il k-d-tree è una struttura di indicizzazione ad albero pensata per la memoria principale, quindi non adatta alla memoria secondaria in quanto non bilanciata e non paginata.
La sigla k-d, sta per [i]k-dimensionality[/b]. È quindi una struttura di indicizzazione per dimensioni maggiori di 1.
Per dimensione, intendiamo un attributo che può variare in un range di valori.
La combinazione di più attributi determina la dimensione maggiore di uno.
Questo tipo di albero utilizza il concetto di partizionamento in intervalli degli assi cartesiani per permettere di indicizzare i valori.
Il k-d-tree è un albero binario di ricerca, in cui ogni livello è etichettato (ciclicamente) con una delle n coordinate ed in ogni nodo è presente un separatore dato dal valore mediano dell'intervallo che si sta partizionando.
La seguente immagine aiuterà nella spiegazione:
In questo caso, vogliamo indicizzare tramite k-d-tree l'insieme di punti mostrato in figura.
Per ogni dimensione (ne abbiamo 2 in questo caso), si inizia suddividendo l'asse in 2 parti, utilizzando come punto per la suddivisione il valore mediano.
In questo modo abbiamo suddiviso il piano in due semipiani distinti. Nella parte di sinistra troveremo i valori minori o uguali al valore mediano, nella parte destra quelli maggiori.
Si passa all'altra coordinata, si effettua la stessa operazione per ogni semipiano venutosi a creare.
Così via fino a che la suddivisione non contiene alcun punto, in tal caso la generazione dell'albero è terminata. Riconducendosi a questa suddivisione:
È quindi possibile effettuare ricerche all'interno di questo albero sfruttando l'ordinamento delle singole coordinate, attraversandolo dalla radice fino alla foglia desiderata, la quale potrà contenere il punto cercato.
Ovviamente il tipo di ricerca varierà a seconda del tipo di query effettuata, in quanto per una window query è necessario trovare valori in un intervallo, quindi sarà necessario scorrere l'albero anche all'indietro (backtraking) se l'intervallo della windows query contiene più regioni.
Quando si deve inserire un nuovo elemento si cerca la foglia che deve contenerlo e se la foglia è piena (overflow) ovviene uno split verso il basso come accade in un albero binario (e non come accade nel B(+|-)tree, dove lo split avviene verso l'alto).
L'albero non è bilanciato e periodicamente richiede una riorganizzazione.
Le cancellazioni sono molto complicate, soprattutto se si vogliono effettuare merge delle foglie in underflow.
Come precedentemente detto, questo albero utilizza il partizionamento in intervalli degli assi cartesiani per poter permettere l'indicizzazione dei valori.
La tecnica mostrata precedentemente usa il partizionamento tramite valore mediano, ma non è la sola possibile.
Esistono diverse varianti per gestire in maniera diversa i separatori, come ad esempio il BSP tree che utilizza degli iperpiani non paralleli agli assi (cosa che con il metodo del valore mediano invece si ha), oppure il VAMsplit kd-tree che sceglie la coordinata migliore di split per ogni nodo come quella avente maggior varianza.