Please enable JavaScript.
Coggle requires JavaScript to display documents.
Rappresentazione Dati Multidimensionali: KD ALBERI, Range Query - Coggle…
Rappresentazione
Dati Multidimensionali:
KD ALBERI
Dati Multidimensionali
informazioni spaziali
k attributi di un record
...
Interrogazioni
Range Queries
ricerca insieme di punti in un intervallo o regione
Nearest-neighbor Queries
punto più vicino al punto specificato
Point Queries
ricerca punto nello spazio con certe coordinate
Partial Match Queries
forniti valori di alcune coordinate, si cercano tutti i punti dell'iperpiano corrispondente
Kd alberi
alberi binari in al livello i si confronta la dimensione i-esima
la ricerca procede a sinistra se < e a destra se >=
maggiore il numero di attributi specificati nella query,
più efficiente la ricerca
sono alberi binari perciò devono essere paginati
impossibile bilanciarli con rotazioni
kd alberi bilanciati
se i dati sono noti a priori, è possibile bilanciare l'albero
Inserire per primo il punto P mediano di S^0[x]
Considerare le sottoliste di S^0[x] a sinistra e a destra di P e ordinarle rispetto al valore della ordinata, ottenendo S^1_l[y] e S^1_r[x] ed inserire i punti mediani di ciascuna sottolista
Ordinare la lista dei punti secondo il valore dell'ascissa
ottenendo la lista S^0[x]
...
costi
si costruiscono all'inizio k liste ordinate, una per ogni dimensione O(kn log2 n)
nei passaggi successivi si selezionano i punti delle liste ordinate: T(n) = n+2T(n/2)
costo totale= O(n log2 n)+ O (kn log 2 n) =
O(kn log2 n)
Query
Partial Match Query
specificando solo t<k chiavi
costi:
tN^(1-t/k)
Range Query
costi:
O(N^(1-1/k)+Z) caso pessimo (Z n° punti nel rango)
O(log_2 N +Z) caso medio
Exact Match Query
specificando il valore di tutte le k chiavi
costi:
O(log2 N) alberi bilanciati
O(N) alberi non bilanciati
Best Match Query
o
Nearest Neighbor
se il database non contiene un record, restituire quello più simile
costo:
bilanciato O(log_2 N)
caso pessimo O(N)
medio O((ln N)^k)
kd alberi non omogenei
i dati vengono memorizzati solo nei nodi esterni,
nei nodi interni contengono solo un valore di chiave e due puntatori
implementazione adatta per memorizzare in memoria esterna
Range Query
tutte le interrogazioni sono riconducibili ad una range query