Transcript of Kyriakos Mouraditis, Spiridon Bakiras, Dimitris Papadias Enrico Bergamini, Enrico Grassi Gruppo 19.
- Slide 1
- Kyriakos Mouraditis, Spiridon Bakiras, Dimitris Papadias Enrico
Bergamini, Enrico Grassi Gruppo 19
- Slide 2
- 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
- Slide 3
- 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 top- k queries, relative agli ultimi dati
arrivati Il risultato delle top-k queries viene costantemente
monitorato in base ai dati pi recenti
- Slide 4
- Argomenti affrontati Studi precedenti Threshold Sorted List
Algorithm (TSLA) Threshold Monitoring Algorithm (TMA) Skyband
Monitoring Algorithm (SMA) Complessit computazionale degli
algoritmi Possibili sviluppi
- Slide 5
- 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
- Slide 6
- 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
- Slide 7
- Lavori precedenti Monitoraggio continuo di k-NN queries
Efficacia della struttura a griglia per memorizzare le tuple e le
celle da vedere nel caso dellarrivo 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
- Slide 8
- 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
- Slide 9
- 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 nave.
- Slide 10
- Modulo di calcolo Top-k Per il calcolo viene scelto il
Threshold Algorithm, per la sua popolarit e i buoni risultati lo
score del k- esimo oggetto nel top-k set. Un dato che non supera
questa soglia non far mai parte dei k oggetti migliori. e nessun
punto in questa regione migliore di TA si ferma quando questa
regione contiene almeno k punti buoni almeno quanto
- Slide 11
- Modulo di manutenzione del risultato Organizzazione delle
strutture: p2p2 Lista delle tuple valide p3p3 p4p4 Testa (vecchi)
Coda (recenti) Lista di tuple valide (con politica FIFO sullordine
di arrivo)
- Slide 12
- Modulo di manutenzione del risultato Organizzazione delle
strutture: Lista ordinata su x 1 p.id p.x 1 Lista ordinata su x 2
p.id p.x 2 Numero di sorted list pari al numero di attributi delle
tuple
- Slide 13
- Modulo di manutenzione del risultato Organizzazione delle
strutture: Viste Top-k Query 1 Query 2 Query m Tabella di view
contenente tante viste materializzate quante sono le queries in
esame
- Slide 14
- Modulo di manutenzione del risultato Organizzazione delle
strutture: Viste Top-k Query 1 Query 2 Query m Update viste Lista
ordinata su x 1 p.id p.x 1 Lista ordinata su x 2 p.id p.x 2 p2p2
Lista delle tuple valide p3p3 p4p4 Testa (vecchi) Coda (recenti)
Calcolo Top-K TA Update liste pnpn Tupla scaduta Tuple in arrivo
p2p2
- Slide 15
- 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 k max > k entries (per evitare ricalcoli
e migliorare lefficienza)
- Slide 16
- 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)
- Slide 17
- 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
dallinizio per ristabilire un nuovo risultato di almeno k
oggetti.
- Slide 18
- 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. pkpk (1,1) x2x2 x1x1 1 1 Regione di
influenza Linea definita da score(p k )=x 1 +2x 2
- Slide 19
- 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.
- Slide 20
- 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 unaltra
struttura: una griglia regolare. La griglia costituita da un array
di celle quadrate di dimensione prefissata Per ogni tupla p e ogni
attributo x i di p, si calcola x i / . Questi numeri rappresentano
le coordinate della cella della griglia che conterr p.
- Slide 21
- 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 lordine di arrivo dei punti
nella sliding window.
- Slide 22
- 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.
- Slide 23
- Strutture di indicizzazione e di supporto Per migliorare
lefficienza 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 lid 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
IL c significa che la influence region di q interseca la cella
c
- Slide 24
- Strutture di indicizzazione e supporto
- Slide 25
- TMA sfrutta un metodo intelligente per la scansione delle celle
della griglia, al fine di ridurre il tempo di elaborazione Heap
Threshold monitoring algorithm (TMA): modulo computazionale
- Slide 26
- c 6,6 p Si crea un heap e si inizializza con la cella avente
max_score pi alto (nellesempio, c 6,6 ). Essendo lunica presente
nellheap, viene estratta, e processata alla ricerca di punti validi
da inserire nella top_list Heap c 6,6 Threshold monitoring
algorithm (TMA): modulo computazionale
- Slide 27
- c 6,6 c 5,6 c 6,5 p p p Heap Se non sono gi presenti, si
inseriscono nellheap tutte le celle adiacenti a quella estratta
(nellesempio, c 5,6 e c 6,5 ) c 5,6 c 6,5 Threshold monitoring
algorithm (TMA): modulo computazionale
- Slide 28
- c 6,6 c 5,6 c 6,5 c 4,6 c 5,5 p p p Heap c 5,6 c 6,5 Lheap deve
essere organizzato in ordine decrescente di max_score (ms) sulle
celle. Si supponga ms(c 5,6 )>ms(c 6,5 ) p domina la regione blu
p domina la regione azzurra Threshold monitoring algorithm (TMA):
modulo computazionale
- Slide 29
- 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, nellheap 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
linserimento di un numero di celle pari alla dimensione.
- Slide 30
- Threshold monitoring algorithm (TMA): modulo di manutenzione
Tipicamente, nel nostro sistema, ad istanti non noti, un insieme di
tuple P ins arriva e un insieme P del scade. Gli scenari pi
interessanti sono due: 1. Le tuple in P ins arrivano dentro la
influence region di qualche query, e i punti in P del non sono
migliori dei nuovi entrati 2. I punti in P ins non cadono dentro la
influence region, e i punti in P del vengono eliminati dalla
influence region.
- Slide 31
- Caso 1 Per prima cosa processo i punti in P ins (P 3 e P 4 )
Per ciascun punto appartenente a P ins,vengono aggiunte delle
entries nelle liste di punti delle rispettive celle (P 3 -> c
5,6, P 4 -> c 4,6 ). x2x2 x1x1 p1p1 p2p2 p3p3 p4p4 P ins = {P 3,
P 4 } P del = {P 1, P 2 }
- Slide 32
- Caso 1 x2x2 x1x1 p1p1 p2p2 p3p3 p4p4 Per ogni cella aggiornata,
si controllano le queries contenute nelle influence list: se lo
score dei nuovi punti migliore del peggiore della lista, il nuovo
arrivato viene inserito nella top_list di quella query e il
peggiore viene rimosso P ins = {P 3, P 4 } P del = {P 1, P 2 }
- Slide 33
- Caso 1 x2x2 x1x1 p1p1 p2p2 p3p3 p4p4 La influence region cambia
con il nuovo inserimento (si riduce). Tuttavia, le influence list
delle celle che non appartengono pi alla influence region non
vengono aggiornate I punti in P del non fanno pi parte della
top_list, perci vengono semplicemente eliminati dalle celle P ins =
{P 3, P 4 } P del = {P 1, P 2 }
- Slide 34
- Caso 2 Siano P ins = P 5 e P del = P 3 Partendo da P ins, poich
lo score di P 5 non migliore di quello attuale, il punto viene
semplicemente inserito nella cella corrispondente x2x2 x1x1 p3p3
p4p4 p5p5 P ins = {P 5 } P del = {P 3 }
- Slide 35
- Caso 2 x2x2 x1x1 p3p3 p4p4 p5p5 La rimozione di P 3 porta al
ricalcolo totale della soluzione top-k. Il nuovo punto migliore
trovato, P 4, modifica la influence region corrispondente alla
query (si espande). P ins = {P 5 } P del = {P 3 }
- Slide 36
- Caso 2 x2x2 x1x1 p3p3 p4p4 p5p5 La query in esame viene poi
rimossa dalla influence list delle celle che non fanno pi parte
della nuova influence region. Laggiornamento viene effettuato
partendo dalle celle rimaste nellheap che precedentemente non erano
state aggiornate, aggiungendo di volta in volta ad una lista le
celle adiacenti allultima aggiornata P ins = {P 5 } P del = {P 3
}
- Slide 37
- 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?
- Slide 38
- Skyline e Skyband: propriet geometrica Definisco Skyline la
linea che contiene tutti i punti che compaiono nel risultato di una
top-1 query qualunque (con scoring function monotona) La skyband
una generalizzazione del concetto di skyline. Una k-skyband la
regione contenente tutti i punti dominati al pi da k-1 punti Dato
un insieme di tuple (ad esempio quelle delle sliding windows) di
numero contenuto, sempre possibile, per ogni tupla, calcolare lo
score globale e tenere traccia del suo istante di arrivo. Essendo
la lista di tuple valide organizzata con politica FIFO, lordine di
scadenza delle tuple coincide con lordine di arrivo
- Slide 39
- Skyline e Skyband: propriet geometrica Se rappresentiamo queste
informazioni in un grafico, si ottiene la figura seguente 1 7 p1p1
p2p2 p3p3 p4p4 p5p5 p6p6 p7p7 p8p8 score Tempo di scadenza 6 5 4 32
1 0
- Slide 40
- Skyline e Skyband: propriet geometrica Introduciamo quindi un
nuovo concetto di dominanza tra tuple: una tupla p 1 domina una
tupla p 2 se e solo se p 1 ha uno score maggiore di p 2 e scade
dopo p 2 Losservazione 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 k- skyband queries indipendente
dalla dimensione delle tuple.
- Slide 41
- Skyband Monitoring Algorithm (SMA) SMA sfrutta la riduzione a
k-skyband query per migliorare lefficienza 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.
- Slide 42
- 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,
ordinata per valori decrescenti di score Successivamente, SMA
calcola, per ciascun punto nella skyband di ogni query, il
dominance counter
- Slide 43
- 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.
- Slide 44
- SMA: modulo di manutenzione Il modulo di manutenzione tiene
traccia dellarrivo 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 laggiornamento dei risultati, evitando
ricalcoli onerosi. Osserviamone il funzionamento attraverso due
esempi chiave.
- Slide 45
- Caso 1 Arrivo di un nuovo dato dominante: Inizialmente, la
skyband composta dai punti riportati (i cui DC sono tra parentesi).
0 1 2 3 4 5 6 7 tempo score (0) p2p2 (1) p3p3 (0) p5p5 (1)
p7p7
- Slide 46
- Caso 1 Arrivo di un nuovo dato dominante: 0 1 2 3 4 5 6 7 tempo
score (0) p2p2 (1) p3p3 (0) p5p5 (1) p7p7 Allistante 3, entra nel
sistema P 9, che domina P 3, P 7 e P 5 p9p9 (0)
- Slide 47
- Caso 1 Arrivo di un nuovo dato dominante: 0 1 2 3 4 5 6 7 tempo
score (0) p2p2 p3p3 p5p5 p7p7 p9p9 Il modulo di manutenzione
aggiorna quindi i DC di questi punti, che vengono eliminati dalla
skyband (se DC K) (2) (1) (2)
- Slide 48
- Caso 1 Arrivo di un nuovo dato dominante: 0 1 2 3 4 5 6 7 tempo
score (0) p2p2 p5p5 p9p9 Il modulo di manutenzione aggiorna quindi
i DC di questi punti, che vengono eliminati dalla skyband (se DC K)
(1)
- Slide 49
- Caso 2 Scadenza di uno dei dati nella skyband 01 2 3 4 5 6 7
tempo score (0) p2p2 p9p9 (1) p5p5 (0) Allistante 5, il punto P 2
scade
- Slide 50
- Caso 2 Scadenza di uno dei dati nella skyband 01 2 3 4 5 6 7
tempo score p9p9 (1) p5p5 (0) Il modulo di manutenzione provvede ad
eliminare P 2 dalla skyband
- Slide 51
- Caso 2 Scadenza di uno dei dati nella skyband 01 2 3 4 5 6 7
tempo score p9p9 (1) p5p5 (0) Poich i rimanenti dati della skyband
escono dal sistema dopo P 2 (non sono dominati da esso), non
necessario alcun aggiornamento dei DC
- Slide 52
- Ancora sul modulo di manutenzione Il modulo di manutenzione
memorizza larrivo di tutti i dati, ma considera le sole tuple con
score maggiore del k-esimo elemento di ogni skyband per
laggiornamento 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
- Slide 53
- 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 laggiornamento 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
- Slide 54
- 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
- Slide 55
- La complessit temporale del modulo computazionale usato sia da
TMA che da SMA T comp = O(ClogC+|C|logk) dove |C| indica il numero
di punti nelle celle processate Analisi delle performance
- Slide 56
- Siano: Q il numero delle queries di interesse Pr rec la
probabilit che dopo gli aggiornamenti il risultato debba essere
ricalcolato ex-novo La complessit temporale totale sar: T TMA = O(r
+ Q(Cr d + krlogk/N + Pr rec T comp )) La memoria richiesta sar: S
TMA = O(N(d+1)+Q(C+d+2k)) Analisi delle performance: TMA
- Slide 57
- Siano: Q il numero delle queries di interesse La complessit
temporale totale sar: T SMA = O(r + Q(Cr d + k 2 r/N)) La memoria
richiesta sar: S SMA = O(N(d+1)+Q(C+d+3k)) Analisi delle
performance: SMA
- Slide 58
- In generale, SMA pi veloce, ma occupa pi memoria. Tuttavia, se
Pr rec molto piccolo, TMA pi efficiente. Questa evenienza comunque
piuttosto rara Lefficienza 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 Analisi delle performance:
considerazioni
- Slide 59
- 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
- Slide 60
- Valutazioni sperimentali Il benchmark di uso comune per queste
applicazioni prevede due fasi di testing, una su dati indipendenti
(IND), laltra 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
- Slide 61
- Valutazioni sperimentali Tempo di elaborazione al variare di d
Tempo di elaborazione al variare di N
- Slide 62
- Valutazioni sperimentali Tempo di elaborazione al variare di r
Tempo di elaborazione al variare di Q
- Slide 63
- Valutazioni sperimentali Tempo di elaborazione al variare di k
Spazio richesto al variare di k
- Slide 64
- 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 leliminazione esplicita dei dati: impossibile
usare SMA perch richiede di conoscere in anticipo lordine di
scadenza dei dati. Nessun problema, invece, con TMA.
- Slide 65
- Conclusioni Dallanalisi 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
- Slide 66
- Grazie per lattenzione Vota gruppo 19!