4.2 Z-order curve
4.2.2 Esempio di generazione della chiave derivata sulla curva Z-order
Z-order
Supponiamo di avere due attributi A1e A0 di valore rispettivamente 3 e 5 e che l’ordine
k della curva sia pari a 4, quindi con attributi che possono assumere valori compresi nell’intervallo [0 ; 15]. La codifica binaria di A1 `e pari a 0011 (va espressa su k bit),
mentre quella di A0`e 0101. La costruzione della chiave derivata ZK di n×k = 2×4 = 8
bits `e data dall’interleaving dei bit delle due chiavi derivate e procede come indicato
in figura 4.7.
Figura 4.7 – Costruzione della chiave derivata sulla curva Z-order 2D
La chiave derivata risultante ZK avr`a una codifica binaria pari a 000110112 di n × k =
4.3
Complessit`a degli algoritmi di generazione del-
la chiave derivata
I due algoritmi di generazione della chiave derivata di Hilbert e della curva Z-order sono molto diversi tra loro. Se l’algoritmo per il calcolo della chiave derivata per la curva Z-order risulta semplice ed immediato in quanto richiede solamente una fusione dei bit dei vari attributi, l’algoritmo per la generazione della chiave derivata di Hilbert al contrario `e molto pi`u complicato e richiede il calcolo preliminare di una tabella di generazione degli stati ed il calcolo ad ogni iterazione di due funzioni particolari, per determinare la matrice dello stato successivo della curva ed una sezione di n bits della chiave derivata.
Figura 4.8 – Mapping di una risorsa mediante curve space-filling diverse
L’algoritmo per il calcolo della chiave derivata sulla curva Z-order esegue una scansione lineare degli n × k bits degli n attributi fondendoli in un’unica chiave di n × k bits. La complessit`a della generazione della chiave derivata per la Z-order curve `e O(k · n). E’ possibile definire un’ottimizzazione per l’algoritmo basata sull’interleaving dei bits, ma tale ottimizzazione diminuisce il tempo di esecuzione dell’algoritmo di un fattore costante e quindi non ne modifica la complessit`a.
L’algoritmo per il calcolo della chiave derivata sulla curva di Hilbert si compone di due parti: la prima parte riguarda il calcolo della tabella di generazione degli stati o
generator table che pu`o essere eseguito una volta soltanto e utilizzata successivamente per la generazione di tutte le chiavi derivate necessarie. La seconda parte dell’algo- ritmo riguarda il calcolo vero e proprio della chiave derivata di Hilbert, formata da n × k bit. Questa parte richiede k iterazioni (con k pari all’ordine di raffinamento della curva) in ognuna delle quali si calcolano le due funzioni f1 e f2 (si veda la sezione
4.1.2). La funzione f1 `e composta da due step successivi: il primo prevede il calcolo
dell’or esclusivo (XOR) tra il valore corrente della variabile zi e l’array signs, che con-
tiene i segni della matrice di trasformazione dello stato corrente, mentre nel secondo si effettua una permutazione dei bit del valore ottenuto come risultato del primo passo a
seconda del valore degli elementi della matrice matrSc corrente. La funzione f2, come
la funzione f1 si compone anch’essa di due step successivi: nel primo si effettua il
calcolo della matrice di trasformazione per il prossimo stato (matrice A), come permu- tazione delle righe della matrice di trasformazione per lo stato successivo ricavata dalla generator table al passo precedente, in base al valore degli elementi della matrice di
trasformazione dello stato corrente attuale. Il secondo step della funzione f2 modifica
i segni degli elementi della matrice A in maniera differente a seconda di alcuni casi particolari dati dalle combinazioni dei segni delle matrici dello stato corrente attuale e di trasformazione per lo stato successivo, ricavata dalla generator table al termine del calcolo della funzione f1.
Analizziamo quindi la complessit`a dell’algoritmo di generazione della chiave deri-
vata per la curva space-filling di Hilbert, definito in figura 4.5. L’algoritmo prevede un loop pi`u esterno di k iterazioni, tante quanto `e l’ordine della curva space-filling. All’interno di questo loop viene eseguito un certo insieme di operazioni di costo O(n).
Ad esempio la costruzione della variabile zi al primo passo richiede la concatena-
zione dei bit corrispondenti delle rappresentazioni degli n attributi. La complessit`a
dell’algoritmo `e quindi O(n · k).
La complessit`a di generazione delle chiavi derivate per i due tipi di curva `e quindi
la stessa. Questa complessit`a `e infatti inerente al problema della generazione della
chiave derivata che richiede un numero di iterazioni pari al numero di suddivisioni
dello spazio e quindi dell’ordine della curva. Per ogni iterazione occorre elaborare
1 bit per ognuna delle coordinate. Si noti per`o che, a differenza della Z-order curve,
la generazione della chiave derivata per la curva di Hilbert richiede l’esecuzione di
operazioni di complessit`a costante ad ogni iterazione. La differenza tra gli algoritmi
costanti sul tempo di esecuzione. Si noti inoltre che il tempo di esecuzione di entrambi
gli algoritmi `e proporzionale al numero di bit richiesti per la rappresentazione della
chiave derivata. C’`e inoltre da considerare che l’algoritmo per la generazione della
chiave di Hilbert richiede la generazione della generator table e che questa pu`o risultare di grande dimensione per valori di n e k elevati. Il numero di righe di questa matrice
risulta pari al numero di chiavi derivate su una curva del primo ordine e quindi 2n.
Ogni riga contiene nelle colonne Y, X1 ed X2 valori di n bits ed una matrice n × n.
Si ottiene quindi una dimensione della matrice di O(2n· 2n) bits. Per valori elevati di
n la dimensione della tabella pu`o assumere quindi dimensioni elevate. Inoltre, come
vedremo nel capitolo 6, gli algoritmi per la risoluzione di query sulla curva Z-order
sono estremamente pi`u semplici. Queste limitazioni hanno portato alla scelta della
HASP: l’architettura
In questo capitolo presentiamo l’architettura generale di HASP. HASP definisce un albero di agggregazione. La struttura dell’albero e le operazioni su di esso sono riprese da XCone. HASP estende XCone per il supporto al caso multidimensionale. Que-
sto implica la necessit`a di inserire la generazione della chiave derivata e cambiare le
strutture di aggregazione ed il metodo di risoluzione delle range query. Nelle prossime
sezioni verr`a prima descritto l’albero XCone e successivamente mostrate le strategie
di aggregazione definite per HASP.
5.1
XCone
XCone [44] `e una rete P2P che nasce come estensione del sistema Cone descritto in
precedenza il quale supporta solamente query del tipo Trova k risorse maggiori di S. In XCone diversamente, grazie ad una struttura ad albero distribuita, costruita al di
sopra di una qualunque DHT, `e possibile definire una strategia di aggregazione delle
risorse tale per cui risulti efficiente risolvere query del tipo Trova k risorse per cui il valore X sia compreso tra V 6 X 6 S .