Kyriakos Mouraditis, Spiridon Bakiras, Dimitris Papadias Enrico Bergamini, Enrico Grassi Gruppo 19.

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 top- k 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 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

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 nave.

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

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)

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

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

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

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)

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 dallinizio 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. pkpk (1,1) x2x2 x1x1 1 1 Regione di influenza Linea definita da score(p k )=x 1 +2x 2

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 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.

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.

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 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

Strutture di indicizzazione e supporto

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

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

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

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

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.

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.

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 }

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 }

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 }

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 }

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 }

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 }

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 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

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

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.

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.

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

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 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.

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

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)

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)

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)

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

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

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

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

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

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 T comp = O(ClogC+|C|logk) dove |C| indica il numero di punti nelle celle processate Analisi delle performance

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

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

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

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), 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

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 leliminazione esplicita dei dati: impossibile usare SMA perch richiede di conoscere in anticipo lordine di scadenza dei dati. Nessun problema, invece, con TMA.

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

Grazie per lattenzione Vota gruppo 19!

Kyriakos Mouraditis, Spiridon Bakiras, Dimitris Papadias Enrico Bergamini, Enrico Grassi Gruppo 19.

Documents

Transcript of Kyriakos Mouraditis, Spiridon Bakiras, Dimitris Papadias Enrico Bergamini, Enrico Grassi Gruppo 19.