Riassunto esame Analysis of algorithms and data structures, Prof. Andrea Marino, libro consigliato Think Python: How to Think Like a Computer Scientist, Allen B. Downey

RETURN

Ciò significa che l’operazione di UNION di due sketches è consistente, ed effettuare

l’unione tra due sketches fornisce lo stesso risultato di creare uno sketch ex-novo

∪

partendo dall’insieme ( )

- nel caso in cui venga chiamata UPDATE( , ) dopo una precedente chiamata a

( ) ( )

UPDATE( , ) con lo stesso lo sketch rimane inalterato, ciò significa che

( )

SIZE( ) ritornerà sempre lo stesso valore

Ora, integrando gli sketches nell’algoritmo del priority sampling, otteniamo:

- per ogni effettua ( )

( )

INIT( )

1

∈ { } ∪ ( )

- per ogni , per ogni , effettua

( )

( )

UPDATE( , )

1

- stampa ( ( )

)

(

)

1

∑ 2

ℎ ∈ 2...

- per :

- per ogni effettua ( ) ( )

( ) = ( )

ℎ ℎ−1

( , )

- per ogni arco effettua

( ) [ ( ) ( )

]

( ) = (

) , (

)

ℎ ℎ ℎ−1

- stampa ( ( )

)

(

)

ℎ

∑ 2

2

( )

Θ ( ) Θ

In questa versione che utilizza gli sketches, l’utilizzo di memoria è rispetto al

( )

( )

della versione standard, in quanto le dimensioni degli sono costanti.

ℎ−1

E’ importante notare che le UPDATE effettuano selezione e quindi le SIZE saranno

un’approssimazione della cardinalità dei vari insiemi.

Vari metodi per implementare matematicamente gli sketches

Di base lo scopo di uno sketch è quello di approssimare insiemi. Questa metodologia non è

stata creata specificatamente per grafi, ma è vastamente utilizzata anche in quest’ambito.

Approccio k-min:

un k-min sketch include l’item di rango più basso in ognuna delle premutazioni

indipendenti.

,...,

Ora, siano ranks tali che:

1 { }

1 2 −1

: → , ,..., ,1

e ( ⊥ ) = ∞

Ciò significa che abbiamo funzioni (maps) che mappano ogni numero dell’universo (di

{ }

1 2 −1

, ,..., , 1

cui è sottoinsieme) in . Il valore indica quanti saranno gli elementi

presenti nello sketch, ed è un valore piccolo e costante.

,...,

In questo caso uno sketch è una sequenza di entries dove ogni entry può essere un

1

⊥

elemento di oppure .

In questo framework, per ognuna delle slot relative alle funzioni memorizzo

l’elemento che ha il valore di ranking minimo per quella specifica funzione.

Riscriviamo quindi le definizioni dei metodi dello sketch in base a queste specifiche:

( ) =⊥ ∀

- init( ): ( )

( ) ∀ 1 ≤ ≤ > ( )

- update( , ): tale che , se , viene rimpiazzato con .

Ciò significa che, per ogni funzione calcolo il mapping di di e se quest’ultimo è

più basso del mapping dell’elemento correntemente in posizione -esima , allora

sostituisco con . NB: con questo metodo (riconducibile al sampling con

( )

> (

)

rimpiazzamento) sono possibili duplicati, nel caso in cui per multipli

valori di . Vi sono altri metodi per evitare questo spreco

{ }

( ) ( ) ,..., = ( )

- union( , ): ritorna tale che . Ciò significa

{ }

1 ∈ ,

che, in modo semplice, per fare l’unione tra due sketches è sufficiente confrontare,

per ognuna delle slot, l’ -esimo elemento del primo con l’ -esimo elemento del

secondo e il minore tra i due finirà nello sketch dell’unione:

( ( ( ) ( ) )

)

∀: ( ∪ ). ,

( )

( ) / ∑ − 1

- size( ): ritorna . Ciò significa che la stima della dimensione

∈

(

)

dell’insieme di partenza è ottenuta tramite la divisione di per la somma dei

rankings degli elementi dello sketches, meno 1. Di base, eseguendo la media tra i

risultati ottenuti da tutte le permutazioni delle possibili , otteniamo uno stimatore

unbiased. −2

( )

= Θ ε

( )

Riprendendo il teorema di Azuma-Hoeffding bounding, prendendo

ε

l’errore relativo è limitato da .

Sia ora il rank minimo degli elementi di . Se i ranks degli elementi di sono distribuiti

uniformemente, allora la probabilità che sia minore di è:

|

|

( ≤ ) = 1 − ( 1 − )

e la probabilità che sia esattamente è: |

|−1

( = ) = |

| ( 1 − )

In particolare il valore atteso è dato da:

1 1

|

|

|

|−1 (

1−

) (

1+

|

|·

) 1 1

⎡⎢ ⎤

[ ] = ∫ · | | ( 1 − ) = − |

| · = ⇒ | | = −1

⎥

|

|

(

1+

|

|

) |

|+1

[

]

⎣ ⎦

0 0

ovvero l’inverso della media meno 1, che è esattamente la formula della size

( )

/ ∑ − 1

∈

(

)

semplicemente rovesciata.

Approccio bottom-k:

dati:

- un ranking (i.e. una funzione biiettiva):

{ }

1 2 −1

: → , ,..., ,1

NB: al contrario del k-min, il bottom-k usa un’unica permutazione

- un subset di

denotiamo con:

(

)

- i primi elementi di in base al ranking . NB: nel caso del k-min si

manteneva in memoria soltanto il primo elemento di ogni permutazione in base al

ranking della -esima funzione , mentre qui si mantengono i primi

→

( )

- il rank del -esimo elemento di in base al ranking qui memorizziamo i

ℎ

rank di ogni elemento in base alla permutazione

Uno sketch bottom-k include i elementi con il più basso ranking in una singola

→

(

)

permutazione, ovvero in questo caso lo sketch è semplicemente un subset di

Riscrivendo i metodi, abbiamo:

( ) ( )

- init( ): è un insieme vuoto

( ) | ( ) | <

- update( , ): se la cardinalità dello sketch è strettamente minore di k,

( ) (

( ( ) ) ) >

(

)

allora viene aggiunto a . Altrimenti, se , rimpiazza

( ( ) )

con . Mantenendo gli elementi dello sketch in ordine crescente, è

sufficiente confrontare il maggiore elemento con . Nel caso in cui sia maggiore

dell’ultimo elemento, non è necessario effettuare altri confronti, in quanto grazie

all’ordine crescente tutti gli altri elementi dello sketch sono sicuramente minori del

( )

massimo. In questo caso paghiamo un costo solo nel caso in cui sia minore

del massimo. Memorizzo gli elementi dello sketch in una heap (un albero in cui il

massimo è sempre la radice, in cui ogni elemento minore della radice viene messo a

( ( ) )

sinistra e ogni elemento maggiore viene messo a destra), così reperisco

(1)

in tempo

( ) ( )

( ) ∪

( )

- union( , ): ritorna i primi elementi del set , ovvero

( (

) ∪ ( ) )

NB: non è necessario considerare gli insiemi di partenza e , è infatti sufficiente

confrontare i due sketch con due indici, partendo confrontando i primi due elementi

di entrambi gli sketches. Nel caso in cui il primo elemento del primo sketch abbia

ranking minore del primo elemento del secondo sketch, scorro il primo indice in

avanti, altrimenti scorro il secondo. Effettuando questo procedimento al più l’unione

()

costerà , seguendo il paradigma del merge sort

−1

( )

- size( ): ritorna (

(

)

)

ℎ −2

( )

= Θ ε

( ) ε

Anche qui abbiamo che scegliendo l’errore relativo è limitato da .

L’idea dietro a questo stimatore è che, in media, si ha che vale la seguente proporzione:

| |: 1 = ( − 1 ): ( )

ℎ

e facendo la media su tutti i possibili rankings si ha che:

⎡⎢ ⎤⎥

−1

| | = (

)

⎣ ⎦

ℎ

Questo si basa sull’idea che, avendo elementi uniformemente distribuiti, nel caso in cui un

1

insieme abbia pochi elementi, il suo elemento capita molto vicino ad , mentre nel

ℎ

caso in cui abbia tanti elementi, il suo elemento capita molto vicino a 0.

ℎ

L’approccio bottom-k corrisponde ad effettuare sampling senza rimpiazzamento, in quanto

non posso avere, come nel caso del k-min, elementi duplicati, dato che i ranking sono tutti

elementi distinti di un’unica permutazione.

Approccio LogLog counters:

( ) ,...,

in questo approccio uno sketch è una sequenza di entries dove ogni entry è

1

una sequenza di bit.

In questo contesto, date funzioni di partizione definite come

: → { 1, 2,..., } 1 ≤ ≤

per ogni con

= 1

si ha che il bit se esiste un elemento in che è mappato in secondo , altrimenti

,

= 0 .

, × 1