Kyriakos Mouraditis, Spiridon Bakiras, Dimitris Papadias
Enrico Bergamini, Enrico Grassi
Gruppo 19
Introduzione
 Ciò che sappiamo:
 Soluzione di top-k queries su database convenzionali
 Ciò che vogliamo fare:
 Monitoraggio continuo di top-k queries su sliding
windows
Scenario di riferimento
 ISP che vuole monitorare pacchetti di dati attraverso
dei router
 I dati sono immagazzinati su un server centrale, e sono
sempre disponibili
 Sul server centrale si ha un numero consistente di topk queries, relative agli ultimi dati arrivati
 Il risultato delle top-k queries viene costantemente
monitorato in base ai dati più recenti
Argomenti affrontati
 Studi precedenti
 Threshold Sorted List Algorithm (TSLA)
 Threshold Monitoring Algorithm (TMA)
 Skyband Monitoring Algorithm (SMA)
 Complessità computazionale degli algoritmi
 Possibili sviluppi
Lavori precedenti
 Top-k queries con dati provenienti da più sorgenti:
 I dati provengono da diverse fonti, ma sono statici
 Viene eseguita una query per volta
 Noi vogliamo:
 Potere eseguire più queries contemporaneamente
 Potere lavorare su dati dinamici
Lavori precedenti
 Monitoraggio di una top-k query distribuita:
 È basato su più fonti, e in questo caso i dati sono
dinamici
 Viene eseguita una sola query
 Si ha molto overhead sulla rete
 Noi vogliamo:
 Operare su una singola fonte multidimensionale
 Lavorare contemporaneamente su più queries
 Minimizzare il tempo di calcolo lato server
Lavori precedenti
 Monitoraggio continuo di k-NN queries
 Efficacia della struttura a griglia per memorizzare le
tuple e le celle da vedere nel caso dell’arrivo di nuovi dati
 C’è una relazione tra le top-k queries e lo skyline.
Verrà utilizzata per ottimizzare uno degli algoritmi
proposti
 Noi vogliamo:
 Utilizzare le strutture di memorizzazione proposte in
questo lavoro per risolvere top-k queries in modo
efficiente
Dettagli tecnici
 Definizione di sliding window
 Count-based: dimensione della finestra limitata da un
numero prefissato di dati
 Time-based: i dati al suo interno sono validi per una
durata di tempo prefissata
 Per mantenere limitato il tempo, i dati relativi alle
sliding windows sono memorizzati in memoria
centrale e indicizzati tramite una griglia regolare.
 Le queries hanno scoring function monotona.
 Lo stream dati segue un modello append-only
Threshold Sorted List Algorithm
 La struttura generale è composta da due moduli
principali:
 Modulo di calcolo top-k
 Modulo di manutenzione del risultato
Il Threshold Sorted List Algorithm definisce un
framework generico per la realizzazione di metodi più
efficienti.
Questo algoritmo sfrutta lavori precedenti, componendo
moduli diversi per fornire un approccio risolutivo
naïve.
Modulo di calcolo Top-k
 Per il calcolo viene scelto il Threshold Algorithm, per
la sua popolarità e i buoni risultati
t è lo score del kesimo oggetto nel
top-k set.
Un dato che non
supera questa soglia
non farà mai parte
dei
k
oggetti
migliori.
TA si ferma quando
questa regione contiene
almeno k punti “buoni”
almeno quanto t...
… e nessun punto
in questa regione è
migliore di t
Modulo di manutenzione del risultato
Organizzazione delle strutture:
Tupla scaduta
p2
Update viste
Update liste
Lista ordinata su x1
Viste Top-k
Query 1
Calcolo Top-K
p.id p.x
Query 2
TA FIFO
Tabella di view
contenente
tante
viste
quante sono
letuple
queries
in esame
Lista
Numero
di
tuple
di sorted
valide
list
(con
parimaterializzate
politica
al numero
disull’ordine
attributi
delle
di arrivo)
1
Lista ordinata su x2
Query m
p.x2
p.id
Update liste
Lista delle tuple valide
p2
p3
Testa (vecchi)
p4
pn
Coda (recenti)
Tuple in arrivo
Update viste
Casi di interesse
Avvio di una nuova top-k query


Eseguo il Threshold algorithm sui dati attualmente
presenti nella sliding window
Il risultato iniziale viene materializzato nella relativa
top-k view, che conterrà kmax > k entries (per evitare
ricalcoli e migliorare l’efficienza)
Casi di interesse
Arrivo di un nuovo dato
 Il nuovo dato viene inserito nella lista di tuple valide
 I suoi attributi vengono inseriti nelle sorted lists
 Per ogni query, viene calcolato lo score globale relativo
alla scoring function
 Eventualmente, viene aggiornato il risultato delle top-k
views e cancellato il risultato peggiore (solo se la lista dei
risultati è piena)
Casi di interesse
Scadenza di un risultato
 Viene rimosso il vecchio dato dalla lista delle tuple valide
 Vengono rimossi gli attributi corrispondenti al dato rimosso
dalle sorted list
 Eventualmente, viene rimosso il dato scaduto dai risultati
delle queries
Qualora la rimozione della vecchia tupla porti alla riduzione
del numero di risultati di una query al di sotto del valore k,
il modulo di calcolo top-k deve essere rieseguito dall’inizio
per ristabilire un nuovo risultato di almeno k oggetti.
Proprietà geometrica
Consideriamo, senza perdita di
generalità, uno spazio unitario
bidimensionale.
Una query risolta restituisce un
insieme di k tuple.
Preso il k-esimo elemento p, è sempre
possibile definire una linea di
separazione sostituendo nella
scoring function gli attributi di p.
Lo spazio da considerare per eventuali
miglioramenti del risultato viene
chiamato “influence region” della
query in esame.
x2
1
Regione di influenza
(1,1)
pk
Linea definita da
score(pk)=x1+2x2
x1
1
Proprietà geometrica
 Tre casi:
1. I dati arrivano fuori dalla regione di influenza: in
questo caso non si fa niente
2. I dati arrivano dentro la regione di influenza: si
calcola il nuovo score e si aggiorna il risultato. La
influence region si rimpicciolisce.
3. I dati dentro la influence region scadono: se ci sono
meno di k oggetti, si ricalcola un nuovo insieme top-k.
La influence region si espande.
Strutture di indicizzazione e di supporto
I dati devono risiedere in memoria centrale
La gestione degli R-tree sarebbe computazionalmente
onerosa, quindi si preferisce utilizzare un’altra
struttura: una griglia regolare.
La griglia è costituita da un array di celle quadrate di
dimensione prefissata d
Per ogni tupla p e ogni attributo xi di p, si calcola  xi/d .
Questi numeri rappresentano le coordinate della cella
della griglia che conterrà p.
Strutture di indicizzazione e di supporto
È inoltre necessaria una lista di punti validi
organizzata con politica FIFO sul tempo di arrivo.
Questa lista rappresenta le sliding windows.
Ogni cella della griglia regolare possiede una lista di
punti validi contenente i puntatori ai punti della
sliding window che si trovano al suo interno. Questa
lista rispetta l’ordine di arrivo dei punti nella sliding
window.
Strutture di indicizzazione e di supporto
 Le varie queries di interesse sono memorizzate in una
tabella. Per ogni query si tiene traccia di:
 Un id univoco
 Il numero k di risultati richiesto
 La scoring function f
 Il risultato attuale top_list
N.B. Il k-esimo risultato congiunto alla scoring function f
definisce implicitamente, per ogni query, la influence
region.
Strutture di indicizzazione e di supporto
Per migliorare l’efficienza del modulo di manutenzione
del risultato, ad ogni cella della griglia è associata una
influence list.
Tale lista è organizzata come una hash table, che
utilizza come chiave l’id delle query.
Questa scelta è motivata dalla necessità di aggiornare
rapidamente le informazioni relative alla regione di
influenza di ogni cella per ogni query.
Il fatto che una query q appartenga alla influence list ILc
significa che la influence region di q interseca la cella c
Strutture di indicizzazione e supporto
Threshold monitoring algorithm (TMA):
modulo computazionale
L’heap
deve
essere
Si
Se
non
crea
sono
un
già
heap
e si
TMA
sfrutta
un
metodo
organizzato
in laordine
inizializza
presenti,
si inseriscono
con
cella
intelligente
per
decrescente
di
avente
nell’heap
tutte
cellepiù
scansionemax_score
dellelecelle
max_score
alto
csulle
adiacenti
a quella
della (nell’esempio,
griglia,
al(ms)
fine di
6,6).
celle.
Sitempo
supponga
Essendo
estratta
presente
ridurre (nell’esempio,
ill’unica
di
ms(c
)>ms(c
cnell’heap,
c6,5
) viene
elaborazione
6,5)estratta,
5,6 e 5,6
p’
domina la regione
blu
e processata
alla ricerca
p’’
la regione
di domina
punti validi
da
azzurra
inserire nella top_list
p’
c4,6
c5,6
p
c6,6
p’’
c5,5
Heap
c5,6
6,6
c6,5
c6,5
Threshold monitoring algorithm (TMA):
modulo computazionale
 A mano a mano che le celle vengono visitate, la top_list
della query si riempie e le influence list delle celle
vengono aggiornate con i riferimenti alle queries in esame
 Il modulo computazionale termina semplicemente una
volta che la top_list raggiunge i k elementi.
 Alla fine del processo, nell’heap rimangono delle celle in
cui max_score è minore o uguale al peggiore risultato
presente nella top_list. Questo fatto verrà sfruttato dal
modulo di manutenzione.
N.B. questo metodo è estendibile per dimensioni crescenti,
tenendo a mente che nel caso peggiore, ad ogni estrazione
corrisponde l’inserimento di un numero di celle pari alla
dimensione.
Threshold monitoring algorithm (TMA):
modulo di manutenzione
Tipicamente, nel nostro sistema, ad istanti non noti, un
insieme di tuple Pins arriva e un insieme Pdel scade.
Gli scenari più interessanti sono due:
1. Le tuple in Pins arrivano dentro la influence region
di qualche query, e i punti in Pdel non sono migliori
dei nuovi entrati
2. I punti in Pins non cadono dentro la influence
region, e i punti in Pdel vengono eliminati dalla
influence region.
Caso 1
La
region
cambia
con
nuovo
(si riduce).
Tuttavia,
le
Perinfluence
ogni cosa
cella
aggiornata,
si ilin
controllano
le queries
contenute
nelle
prima
processo
i punti
Pins (Pinserimento
3 e P4)
influence
list
appartengono
più alla
influence
region
influence
list:delle
seappartenente
locelle
scoreche
deinon
nuovi
punti è migliore
del
peggiore
della
Pernon
ciascun
punto
a
P
,vengono
aggiunte
delle
entries
nelle
ins
vengono aggiornate
lista,
il punti
nuovodelle
arrivato
viene celle
inserito
nella
top_list
di
quella
querydalle
e il
liste
di
rispettive
(P
->
c
,
P
->
c
)
eliminati
5,6 top_list,
4
4,6 perciò vengono
I punti
in viene
Pdel rimosso
non fanno più parte3 della
peggiore
celle.
semplicemente
eliminati dalle celle
Pins = {P3, P4}
Pdel = {P1, P2}
x2
p2
p4
p3
p1
x1
Caso 2
La
query
rimossa dalla influence list delle celle che non
Siano
Pinsin=esame
Pdi
P3viene
= Ppoi
La
rimozione
porta
5 eP
del
3 al ricalcolo totale della soluzione top-k. Il
fanno più parte della nuova influence region. L’aggiornamento viene
Partendo
da Pmigliore
poiché
lorimaste
score
di modifica
P5 non
migliore
di quello
nuovo
punto
trovato,
P4,nell’heap
influence
region
ins, dalle
effettuato
partendo
celle
cheèla
precedentemente
non
attuale,
il
punto
viene
semplicemente
inserito
nella
cella
corrispondente
alla query
(si espande).
erano state aggiornate,
aggiungendo
di volta in volta ad una lista le celle
corrispondente
adiacenti
all’ultima aggiornata
Pins = {P5}
Pdel = {P3}
x2
p4
p3
p5
x1
Problema
Il
ricalcolo totale (oneroso dal punto di vista
computazionale) si ha quando uno dei punti che
scadono fa parte della top_list di una query, e nessuno
dei nuovi arrivi ha uno score migliore del punto
appena scaduto.
Come risolverlo?
Skyline e Skyband:
proprietà geometrica

Skyline queste
la linea informazioni
che contiene in
tutti
punti che
SeDefinisco
rappresentiamo
un i grafico,
si
compaiono
nel risultato
di una top-1 query qualunque (con
ottiene
la
figura
seguente
scoring function monotona)
 La skyband èscore
una generalizzazione del concetto di skyline.
1
Una k-skyband
è pla regione
contenente tutti i punti
p
dominati al più da k-1 punti
 Dato un insieme di tuplep (ad esempio quelle delle sliding
p
windows) di numero
contenuto, pè sempre possibile, per
ogni tupla, calcolare lo score globale e tenere traccia del suo
istante di arrivo. p
p
 Essendo la lista di tuple valide
organizzata con politica
p
FIFO, l’ordine di scadenza
delle tuple coincide con l’ordine
Tempo di
di arrivo
scadenza
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
Skyline e Skyband:
proprietà geometrica
 Introduciamo
quindi un nuovo concetto di
dominanza tra tuple: una tupla p1 domina una tupla
p2 se e solo se p1 ha uno score maggiore di p2 e scade
dopo p2
 L’osservazione importante è che i dati appartenenti
alla k-skyband nello spazio score/time sono quelli che
fanno effettivamente parte dei risultati finali delle
queries. Inoltre, la riduzione da top-k queries a kskyband queries è indipendente dalla dimensione
delle tuple.
Skyband Monitoring Algorithm (SMA)
 SMA sfrutta la riduzione a k-skyband query per
migliorare l’efficienza del modulo di manutenzione
 Introduciamo il concetto di dominance counter DC:
esso rappresenta, per ogni tupla, il numero di tuple
che dominano (secondo la definizione vista) la tupla in
esame nello spazio time/score
 Il DC serve per escludere dalla k-skyband i punti che
sono dominati da almeno altri k punti
 Si noti che il DC è relativo alla scoring function della
query in esame, quindi cambia con essa.
SMA: modulo computazionale
 Per prima cosa, per ogni query viene applicato il
modulo computazionale di TMA
 Il risultato viene memorizzato in una lista skyband che
contiene k entries del tipo <id, score, DC>, ordinata
per valori decrescenti di score
 Successivamente, SMA calcola, per ciascun punto nella
skyband di ogni query, il dominance counter
SMA: modulo computazionale
 Per efficienza del tempo di calcolo, il tempo di arrivo
di ogni tupla processata ed appartenente alla skyband
viene memorizzato in un balanced tree (in ordine
decrescente)
 In questo modo, il DC di ogni tupla è semplicemente il
numero di tuple che lo precedono nel B-tree
 Ciascun nodo interno contiene la cardinalità del suo
sottoalbero: tempo di calcolo O(k logk)
 I DC così calcolati vengono inseriti nella skyband, e i
balanced tree eliminati.
SMA: modulo di manutenzione
 Il modulo di manutenzione tiene traccia dell’arrivo di
tutti i dati (anche quelli non contenuti nello skyband)
e della loro scadenza, aggiornando contestualmente la
struttura dati già presentata per TMA.
 In più, gestisce i DC in modo da ottimizzare
l’aggiornamento dei risultati, evitando ricalcoli
onerosi.
 Osserviamone il funzionamento attraverso due esempi
chiave.
Caso 1
Arrivo di un nuovo dato dominante:
All’istante
nel sistema
Paggiorna
P3,iriportati
PDC
Inizialmente,
la
skyband
è composta
daiquindi
punti
Il
modulo 3,dientra
manutenzione
9, che domina
7 e Pdi
5
questi
punti,
vengono eliminati dalla skyband (se
(i cui DC
sonoche
tra parentesi).
DC ≥ K)
score
p2
(0)
p9
p3
(0)
(2)
(1)
p5
(0)
(1)
p7
(2)
(1)
tempo
0
1
2
3
4
5
6
7
Caso 2
Scadenza di uno dei dati nella skyband
Poiché
i rimanenti
datiPdella
skyband
escono
dal sistema
All’istante
5, ilmanutenzione
punto
Il
modulo
di
provvede
ad eliminare
P2
2 scade
dopo skyband
P2 (non sono dominati da esso), non è necessario
dalla
alcun aggiornamento dei DC
score
p2
(0)
p9
(0)
p5
(1)
tempo
0
1
2
3
4
5
6
7
Ancora sul modulo di manutenzione
 Il modulo di manutenzione memorizza l’arrivo di tutti
i dati, ma considera le sole tuple con score maggiore
del k-esimo elemento di ogni skyband per
l’aggiornamento del risultato
 Tali tuple aggiornano la skyband nella posizione data
dal loro score. I DC degli eventuali dati a score
inferiore devono quindi essere incrementati di una
unità
 Qualora i DC di qualche dato raggiungano il valore k,
questi devono essere rimossi dalla skyband
Ancora sul modulo di manutenzione
 Quando un dato scade, siamo certi che nessun altra
tupla della skyband sia più dominata da esso.
Perciò, non è necessario l’aggiornamento di alcun DC
 Un caso particolare si ha quando la skyband contiene
meno di k tuple
 SOLO in questo caso, il modulo di manutenzione
richiama il modulo computazionale per avere una
nuova skyband
Analisi delle performance
 Assumendo che:
 La cardinalità media dei dati in ogni istante sia N
 Le tuple siano distribuite uniformemente in uno spazio
unitario d-dimensionale
 Lo stream rate sia in media di r tuple per ogni ciclo di
processo
 ogni cella della griglia contiene in media N∙δd punti,
dove δ rappresenta la dimensione di una singola cella
lungo un asse
 Sia inoltre C=O(k/(N∙δd)) il numero medio di celle
processate
Analisi delle performance
 La complessità temporale del modulo computazionale
usato sia da TMA che da SMA è
Tcomp= O(C∙logC+|C|∙logk)
dove |C| indica il numero di punti nelle celle
processate
Analisi delle performance: TMA
 Siano:
 Q il numero delle queries di interesse
 Prrec la probabilità che dopo gli aggiornamenti il
risultato debba essere ricalcolato ex-novo
 La complessità temporale totale sarà:
TTMA = O(r + Q∙(C∙r∙δd + k∙r∙logk/N + Prrec∙Tcomp))
La memoria richiesta sarà:
STMA = O(N∙(d+1)+Q∙(C+d+2∙k))
Analisi delle performance: SMA
 Siano:
 Q il numero delle queries di interesse
 La complessità temporale totale sarà:
TSMA = O(r + Q∙(C∙r∙δd + k2∙r/N))
La memoria richiesta sarà:
SSMA = O(N∙(d+1)+Q∙(C+d+3∙k))
Analisi delle performance:
considerazioni
 In generale, SMA è più veloce, ma occupa più
memoria. Tuttavia, se Prrec è molto piccolo, TMA è
più efficiente. Questa evenienza è comunque
piuttosto rara
 L’efficienza di entrambi i metodi dipende da k, Q, N ed
r, e dalla dimensione δ delle celle: celle grandi
minimizzano il tempo necessario alle operazioni di
heap, ma portano a processare punti esterni alla
influence region; si riduce, inoltre, la necessita di
spazio di memoria
Valutazioni sperimentali
 I test sono stati effettuati con i seguenti parametri,
variandone uno per volta e mantenendo gli altri al
valore di default:
 La macchina utilizzata per le simulazioni disponeva di
un processore Pentium IV a 3,2 GHz e di 1 GB di
memoria RAM
Valutazioni sperimentali
 Il benchmark di uso comune per queste applicazioni
prevede due fasi di testing, una su dati indipendenti
(IND), l’altra su dati anticorrelati (ANT).
 Mentre per i primi i valori degli attributi sono scelti in
modo uniformemente indipendente, i secondi
prevedono la presenza di un attributo dominante fra
tutti
Valutazioni sperimentali
Tempo di elaborazione
al variare di d
Tempo di elaborazione
al variare di N
Valutazioni sperimentali
Tempo di elaborazione
al variare di r
Tempo di elaborazione
al variare di Q
Valutazioni sperimentali
Tempo di elaborazione
al variare di k
Spazio richesto
al variare di k
Possibili modifiche e scenari
alternativi
 Monitoraggio di top-k query con vincoli sugli
attributi: è sufficiente modificare gli algoritmi per
tenere conto della regione di interesse
 Threshold query che richede il monitoraggio di tutti i
punti al di sopra della soglia: è possibile usare TSL, con
le liste al posto degli heap (ordine di visita irrilevante)
 Monitoraggio di top-k queries su uno stream che
prevede l’eliminazione esplicita dei dati: è
impossibile usare SMA perché richiede di conoscere in
anticipo l’ordine di scadenza dei dati. Nessun
problema, invece, con TMA.
Conclusioni
 Dall’analisi sperimentale si nota come SMA sia il più
veloce tra i metodi proposti al variare dei parametri del
problema, a discapito di una lieve maggiorazione dello
spazio occupato
 Possibili lavori futuri potrebbero trattare la risoluzione
di queries con funzioni di preferenza non
monotone. Gli autori suggeriscono il possibile
impiego di ragionamenti geometrici per una
risoluzione efficiente di questo problema
Grazie per l’attenzione
Vota gruppo 19!