In questo sezione verranno illustrate le propriet`a di clustering rispetto a range query n- dimensionali di tre curve presentate: la curva di Hilbert, la curva Gray-code e la curva Z-order. Data una range query definita su uno spazio n-dimensionale come un iper- rettangolo, si definisce cluster un gruppo di punti appartenenti alla regione descritta dalla range query che sono consecutivi sulla curva. Come misura del clustering di una curva si utilizza il numero medio di cluster di punti all’interno del sotto-spazio
definito dalla range query. In figura 3.15 `e mostrato un esempio di come la stessa
query bidimensionale di forma rettangolare Sx × Sy produca due cluster sulla curva
Figura 3.15 – Esempio cluster generati sulla Z-curve (a) e sulla curva di Hilbert (b) dalla stessa query Sx × Sy
Un primo confronto tra le propriet`a di clustering delle tre curve space-filling in oggetto, considerando solo range query di dimensione 2×2, `e stata effettuato da Jagadish in [36]: la curva risultante che minimizza il numero di cluster `e la curva di Hilbert (2), seguita dalla curva Gray-code (2.5) e dalla curva Z-order (2.625). I numeri all’interno delle parentesi successive al nome della curva indicano il numero medio di cluster generati per una range query di dimensione 2 × 2. In seguito, da parte di Rong e Faloutsos
in [37], `e stata formulata un’espressione in forma chiusa del numero medio di cluster
generati da una range query sulla curva Z-order che nel caso di range query 2 × 2 ha dato lo stesso risultato di 2.625 cluster di media calcolato in precedenza da Jagadish. In generale, il numero medio di cluster sulla curva Z-order tende al valore dato dalla somma di un terzo del perimetro del rettangolo della range query con i due terzi del lato del rettangolo descritto dalla range query nella direzione sfavorita. All’inizio del
1997, da parte di Jagadish in [38], `e stata trovata un’espressione in forma chiusa del
numero medio di cluster generati anche per la curva di Hilbert in due dimensioni a partire da range query di forma quadrata 2 × 2 e 3 × 3.
Un’analisi del numero di cluster generati da una query iper-rettangolare `e impor-
tante per le applicazioni che utilizzano le curve space-filling. Ad esempio, nei database in cui uno spazio multidimensionale di attributi viene mappato su uno spazio disco
unidimensionale, il numero di cluster corrisponde al numero di accessi non consecutivi al disco per il reperimento dei dati.
Nel caso di HASP, il numero di cluster, influenza il numero di confronti che devono essere effettuati tra i cluster generati appartenenti alla range query e le aggregazioni di chiavi derivate contenute nei nodi dell’albero HASP.
Sia Nn il numero medio di cluster dentro un iper-rettangolo di n-dimensioni, il
calcolo del numero medio di cluster formati da una range query rettangolare sulla
curva di Hilbert di dimensione n e ordine k , denotata come Hn
k, `e formulato in [35]
ed `e espresso dal seguente teorema:
Teorema 3.6.1. In uno spazio n-dimensionale sufficientemente ampio mappato me-
diante la curva di Hilbert di dimensione n e ordine k, Hn
k, sia Sq l’area totale della
superficie di una query q, allora vale: lim
k→∞Nn = Sq
2n
La dimostrazione del teorema pu`o essere trovata in [35].
Grazie al precedente teorema `e possibile affermare che la curva di Hilbert possiede
un grado di clusterizzazione migliore rispetto alla curva Z-order. Nel caso bidimensio-
nale infatti, il numero medio di cluster per la curva di Hilbert `e approssimativamente
pari ad un quarto del perimetro del rettangolo descritto dalla range query, mentre per
la Z-order curve `e pari circa alla somma di un terzo del perimetro del rettangolo della
range query con i due terzi del lato del rettangolo nella direzione sfavorita. Un corollario al teorema precedente `e il seguente:
Corollario 3.6.2. In uno spazio n-dimensionale sufficientemente ampio mappato sulla
curva di Hilbert di dimensione n e ordine k, Hn
k, sono soddisfatte le seguenti due
propriet`a:
• dato un iper-rettangolo s1× ... × sn, il numero medio di cluster `e pari a:
lim k→∞Nq= 1 n n P i=1 (s1 i n Q j=1 sj)
• dato un iper-cubo di lato s, il numero di cluster `e pari a: lim
k→∞Nn= s n−1
Il teorema precedente indica che se la dimensione della griglia cresce all’infinito, il
numero medio di cluster tende a diventare met`a dell’area di una certa query diviso per
il numero di dimensioni dello spazio. Non indica per`o quanto rapidamente si abbia
la convergenza verso questo valore, valido solo per il risultato medio e non indica
niente circa la varianza dei risultati rispetto al caso medio. Per questa ragione `e
interessante riportare anche i risultati sperimentali ottenuti in [35]. Nelle figure 3.16 e 3.17 sono mostrati i risultati sperimentali ottenuti da una simulazione esaustiva eseguita su uno spazio bidimensionale di grandezza 1K × 1K e da una simulazione statistica su uno spazio tridimensionale 32K × 32K × 32K per ciascuna delle tre curve space-filling in esame al fine di determinare quale curva generi un minor numero di cluster sia nel caso medio che nel caso pessimo [35]. Nelle figure 3.16(a) e (b) vengono riportati i risultati per query rispettivamente di forma quadrata e circolare in uno spazio bidimensionale. Nelle figure 3.16(c) e (d) vengono riportati gli stessi risultati per uno spazio tridimensionale. Si riportano rispettivamente i risultati al variare della lunghezza del lato del quadrato e del raggio del cerchio.
Si noti come nel grafico in figura 3.16(a), i risultati per la curva Z-order e per la curva Gray-code sono esattamente uguali. La curva di Hilbert ottiene un grado di clu- sterizzazione decisamente migliore rispetto alle altre due curve sia nel caso medio che nel caso pessimo. Ad esempio, per una query di forma quadrata nello spazio bidimen- sionale, la curva di Hilbert genera un numero nettamente inferiore di cluster, con un miglioramento rispetto alle altre due curve fino a circa il 48% nel caso medio e al 43% nel caso peggiore. Nel caso di una query sferica, quindi in uno spazio tridimensionale,
la curva di Hilbert `e caratterizzata da una riduzione del numero di cluster nel caso
peggiore rispetto alla curva Z-order fino al 28% e rispetto alla curva Gray-code fino al 18%, mentre nel caso medio, rispetto alla curva Z-order, la curva di Hilbert genera un numero di cluster inferiore fino al 31%, mentre rispetto alla curva Gray-code fino al 22% meno. E’ importante notare come non sempre la curva Gray-code generi un
numero di cluster minore rispetto alla curva Z-order e come ci`o `e in contrasto con
lo studio precedente [36], nel quale la curva Gray-code otteneva una miglior grado di clustering rispetto alla curva Z-order nel caso di query di forma quadrata 2 × 2. In particolare per query di forma circolare bidimensionali, figura 3.16(b) e 3.17(b), la curva Gray-code si comporta in maniera peggiore rispetto alla curva Z-order sia nel caso medio che nel caso peggiore. Al contrario, per query di forma quadrata in uno spazio bidimensionale, la curva Gray-code si rivela migliore nel numero di cluster nel
caso medio rispetto alla curva Z-order per una quantit`a trascurabile (figura 3.17(a)), mentre le due curve ottengono la stessa misura di clustering nel caso pessimo (figura 3.16(a)). In uno spazio tridimensionale invece, la curva Gray-code si rivela decisamen- te migliore rispetto alla curva Z-order per entrambi i tipi di query sia nel caso medio che nel caso peggiore.
Figura 3.16 – Numero di cluster nel caso peggiore per tre differenti curve space-filling
Figura 3.17 – Numero medio di cluster per tre differenti curve space-filling