Albero k-d

Questa voce sull'argomento informatica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento.

In informatica, un k-d tree o albero k-d (abbreviazione di albero k-dimensionale) è una struttura dati utilizzata per il partizionamento dello spazio e finalizzata all’organizzazione dei punti in uno spazio k-dimensionale, ossia definito esattamente da k assi ortogonali, un dato numero finito di dimensioni.^[1]

Introdotto nel 1975 da Jon Louis Bentley, l'albero k-d è una struttura dati utile in diverse applicazioni, quali:

• Ricerche che coinvolgono una chiave di ricerca multidimensionale^[2][3]
  • ad esempio, ricerche per intervallo e ricerche del vicino più prossimo per l'algoritmo k-NN;
  • ricerca di punti di interesse vicini a una coordinata GPS (ad es. "trova il ristorante più vicino") nei Sistemi Informativi Geografici (GIS)
• Creazione di nuvole di punti:
  • in computer grafica e visione artificiale, viene utilizzato per il ray tracing e per la ricostruzione di nuvole di punti 3D (ad es. dati LiDAR).

L'albero k-d è un albero binario in cui ogni nodo è un punto k-dimensionale, un caso particolare di albero binario di partizionamento dello spazio.^[4] Ogni nodo non-foglia può essere considerato come generatore implicito di un iperpiano separatore che divide lo spazio in due parti, note come semispazi. I punti a sinistra di questo iperpiano sono rappresentati dal sottoalbero sinistro di quel nodo, mentre quelli a destra dell'iperpiano sono rappresentati dal sottoalbero destro.

In generale la direzione dell'iperpiano viene scelta nel modo seguente: ogni nodo dell’albero è associato a una delle k dimensioni, con l'iperpiano perpendicolare all’asse di quella dimensione. Quindi, ad esempio, se per una particolare divisione viene scelto l’asse “x”, tutti i punti nel sottoalbero con un valore di “x” inferiore a quello del nodo appariranno nel sottoalbero sinistro e tutti i punti con un valore di “x” maggiore saranno nel sottoalbero destro. In tal caso, l'iperpiano sarebbe determinato dal valore di x del punto e la sua normale sarebbe l’asse x unitario.^[5] La scelta dell'asse di divisione e del punto di partizionamento (split) varia a seconda dell'implementazione, ma l'approccio standard (proposto da Bentley) segue queste regole:

• Rotazione degli assi: si seleziona l'asse di divisione in base alla profondità del nodo nell'albero. Ad esempio, in uno spazio tridimensionale (k=3), la radice divide lungo l'asse x (profondità 0), il livello successivo lungo l'asse y (profondità 1), quello dopo lungo l'asse z (profondità 2), per poi ricominciare dall'asse x (profondità 3). In generale, l'asse è dato da:

${\displaystyle {\textit {asse}}={\textit {profondit}}{\grave {a}}\mod k}$

• Scelta della mediana: per garantire che l'albero sia bilanciato, il punto di split viene scelto calcolando la mediana delle coordinate dei punti lungo l'asse selezionato.

Le principali operazioni sono relative alla creazione della struttura e alla ricerca all'interno della stessa.

La costruzione di un albero k-d a partire da un insieme di N punti avviene in modo ricorsivo:

• Si seleziona l'asse corrente.
• Si ordina il set di punti in base alla coordinata dell'asse e si trova la mediana.
• Il punto mediano diventa il nodo corrente.
• Si applica la procedura ricorsivamente sui punti a sinistra e a destra della mediana.

Se la mediana viene calcolata in tempo lineare utilizzando un algoritmo come Quickselect, il tempo di costruzione totale è ottimale e pari a ${\displaystyle {\mathcal {O}}(N\log N)}$.

La ricerca del vicino più prossimo o NNS (Nearest Neighbor Search) mira a trovare il punto nell'albero più vicino a un punto di query Q. L'algoritmo sfrutta le proprietà geometriche dell'albero per eliminare ("potare") interi rami senza doverli esplorare:

• Discesa: si scende attraverso l'albero come in una normale ricerca binaria per trovare la foglia in cui si troverebbe Q;
• Salita e Verifica: si calcola la distanza tra Q e il punto corrente. Se è inferiore alla distanza minima attuale, diventa il nuovo "migliore";
• Potatura: prima di risalire al nodo padre, l'algoritmo controlla se l'iperpiano di divisione del nodo interseca una sfera ipotetica centrata in Q con raggio pari alla distanza minima corrente; se non c'è intersezione, l'intero sottoalbero opposto viene scartato, garantendo un grande risparmio computazionale.

La complessità delle operazioni su un albero k-d dipende fortemente dal bilanciamento dell'albero e dal numero di dimensioni k:

Operazione	Caso Ottimo / Medio	Caso Peggiore
Spazio di memoria	${\displaystyle {\mathcal {O}}(N)}$	${\displaystyle {\mathcal {O}}(N)}$
Costruzione	${\displaystyle {\mathcal {O}}(N\log N)}$	${\displaystyle {\mathcal {O}}(N\log N)}$ [c 1]
Ricerca NNS	${\displaystyle {\mathcal {O}}(\log N)}$	${\displaystyle {\mathcal {O}}(N)}$
Query di intervallo	${\displaystyle {\mathcal {O}}(N^{1-{\tfrac {1}{k}}}+M)}$[c 2]	${\displaystyle {\mathcal {O}}(N)}$

• k-d tree nella documentazione di scikit-learn

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica