Efficient Top-k Query Evaluation on Probabilistic Data Christopher Ré, Nilesh Dalvi, Dan Suciu University of Washington Presentazione di: Giacomo Aceto, Michele Dinardo, Vito La Porta Relatore: Michele Dinardo Visione di alto livello DBMS: risposte esatte su dati precisi I dati sono spesso imprecisi Match tra oggetti di database diversi Dati estratti automaticamente da testi Database probabilistici gestiscono l’imprecisione La valutazione delle query SQL è NP-completa Molte risposte dovute a improbabili corrispondenze Utente interessato alle risposte di alta qualità Efficiente Top-k, ordinato per probabilità 5 marzo 2008 Efficient Top-k Query Evaluation on Probabilistic Data 2 Overview 5 marzo 2008 Esempio motivante e nozioni di base Multisimulazione Risultati sperimentali Efficient Top-k Query Evaluation on Probabilistic Data 3 Scenario In quali anni ci Anthony Sul web sono Hopkins èmolte apparso in film conrecensioni alta votazione? Recensioni Quali attorifaccio di Pulp Come a Fiction sono apparsi in due film sapere a quali scarsi nei cinque anni film si riferiscono? precedenti a Pulp Fiction? • • IMDB 5 marzo 2008 • Alice necessita di fare estrazione Grande interesse per i dati riguardanti film Un database probabilistico e riconciliazione di datipuò (attori, registi, ecc) aiutare Alice a memorizzare e Dati ben mantenuti e precisi Alice necessita analisi interrogare i suoi di dati incerti Ma mancano le recensioni… di confidenza Efficient Top-k Query Evaluation on Probabilistic Data 4 Riconciliazione di dati asin Title a282 12 Monkeys Recensioni di Amazon a845 Mokey Love asin mid p a282 m897 0.5 a282 m389 0.4 a282 m656 0.1 Tabella di match che cattura l’incertezza mid Title a845 m897 0.3 m897 Twelve Monkeys a845 m845 0.3 Monk m845 Love Story 5 marzo 2008 1 Dati di IMDB m389 Twelve Monkeys (1995) m656 1 [ACG02], [CGG03] e [HS95] per score di similarità automatizzati Efficient Top-k Query Evaluation on Probabilistic Data 5 Tuple come variabili booleane Associamo variabili booleane alle tuple e1 e2 asin mid p a282 m897 0.5 a282 m389 0.4 true se ti è presente ei false altrimenti Ogni istruzione SQL costruisce un’espressione di variabili booleane, secondo l’algebra relazionale probabilistica ([FR97]) 5 marzo 2008 Efficient Top-k Query Evaluation on Probabilistic Data 6 Cenni alla Selezione asin mid a282 m389 e2 mid'm389' 5 marzo 2008 asin mid p a282 m897 0.5 a282 m389 0.4 Efficient Top-k Query Evaluation on Probabilistic Data e1 e2 7 Cenni al Prodotto Incrociato asin mid a282 m897 a282 m389 e1 f1 e2 f1 f1 5 marzo 2008 asin p asin mid p a282 0.5 a282 m897 0.5 a282 m389 0.4 Efficient Top-k Query Evaluation on Probabilistic Data e1 e2 8 Cenni alla Proiezione asin a282 5 marzo 2008 e1 e2 asin asin mid p a282 m897 0.5 a282 m389 0.4 Efficient Top-k Query Evaluation on Probabilistic Data e1 e2 9 Formule DNF su Tuple Obiettivo: ottenere una formula DNF ti Ei ei11 ei1r ei21 ei2r eim1 eimr pti probabilit à DNF SAT Ma DNF SAT è NP-completo... 5 marzo 2008 E qui entrano in gioco gli algoritmi approssimativi... Efficient Top-k Query Evaluation on Probabilistic Data 10 Metodo Monte Carlo: intuizione Superficie terreno = 1000 m² X colpi di cannone N numero palle cadute sulla terra superficieterreno X superficielago X N Come calcolare la superficie del lago? superficie lago X N superficieterreno X superficielago 1000 superficielago 500 superficielago 333. 3 … superficielago 375 5 marzo 2008 Efficient Top-k Query Evaluation on Probabilistic Data 11 Algoritmo di Luby-Karp [LK84] Dopo N passi di simulazione garantisce, con alta probabilità, che: pEi a N , b N intervallo di confidenza La simulazione Incertezza sulla riduce probabilità l’incertezza aN bN 0.0 5 marzo 2008 1.0 Efficient Top-k Query Evaluation on Probabilistic Data 12 Simulazione Naive Per ogni tupla candidata, applica l’algoritmo di Luby-Karp fino a quando l’intervallo non raggiunge un’ampiezza prefissata ε (N libero). ε 0.0 1.0 1 4 Christopher Walken 2 3 ε Samuel L. Jackson Harvey Keitel Bruce Willis 5 marzo 2008 Efficient Top-k Query Evaluation on Probabilistic Data 13 Analisi della Simulazione Naive Non è proprio il meglio che possiamo avere... Esempio: • i = 4 • k = 2 ε troppo piccolo 5 marzo 2008 Efficient Top-k Query Evaluation on Probabilistic Data ε troppo grande 14 Overview 5 marzo 2008 Esempio motivante e nozioni di base Multisimulazione Risultati sperimentali Efficient Top-k Query Evaluation on Probabilistic Data 15 Multisimulazione k-separazione: esiste un insieme T di k intervalli tale che nessuno di essi è annidato ad un intervallo non appartenente a T. Es.: k = 2 T Christopher Walken Samuel L. Jackson Harvey Keitel Bruce Willis 5 marzo 2008 Efficient Top-k Query Evaluation on Probabilistic Data 16 Idea chiave: Regione Critica Ad ogni passo, la regione critica è l’intervallo: c, d kesimoai , k 1esimobi Es.: k = 2 Mitico!!! Quando la ...otteniamo la ragione critica k-separazione diventa vuota... 5 marzo 2008 Efficient Top-k Query Evaluation on Probabilistic Data 17 Algoritmo MS_TopK MS _ TopK (G, k ) : / * G n tuple candidate * / Assegna a1 , b1 an , bn 0,1 while c d do Caso 1 : scegli un double cro sser da simulare Caso 2 : scegli un upper/lowe r crosser da simulare Caso 3 : scegli un un crosser massimale da simulare Update c, d end while return T 5 marzo 2008 Efficient Top-k Query Evaluation on Probabilistic Data 18 Algoritmo MS_RankK Algoritmo ricorsivo che classifica le top-k tuple Tk MS _ TopK (G, k ) Tk 1 MS _ TopK(Tk ,k 1) Tk 2 MS_TopK(Tk 1,k 2) T1 MS_TopK(T2 ,1) Es.: k = 2 G1 T2 G1 ,G4 G2 T1 G1 G3 1 2 G4 5 marzo 2008 Efficient Top-k Query Evaluation on Probabilistic Data 19 Overview 5 marzo 2008 Esempio motivante e nozioni di base Multisimulazione Risultati sperimentali Efficient Top-k Query Evaluation on Probabilistic Data 20 Dettagli sull’esperimento Tabella di match Numero Tuple Match tra titoli 339k Match tra attori 6758k Match tra registi 18k Amazon Recensioni 5 marzo 2008 IMDB Attori Efficient Top-k Query Evaluation on Probabilistic Data Film 21 Tempo di esecuzione In quali anni Anthony Hopkins è apparso in film con alta votazione? 5 marzo 2008 Il metodo naive impiega circa 20 minuti La multisimulazione ha tempi di risposta nettamente migliori Efficient Top-k Query Evaluation on Probabilistic Data 22 Numero Totale di Simulazioni Quali attori di Pulp Fiction sono apparsi in due film scarsi nei cinque anni precedenti a Pulp Fiction? 5 marzo 2008 RankK trae benefici da valori bassi di k; Per TopK il numero di step è indipendente da k; Efficient Top-k Query Evaluation on Probabilistic Data 23 Conclusioni OPT: Algoritmo non deterministico ottimale che conosce il numero di passi da simulare Confronto con OPT: La multisimulazione compie al più il doppio dei passi di simulazione rispetto a OPT Nessun algoritmo deterministico è migliore su ogni istanza 1) 2) Estensione: 5 marzo 2008 Algoritmo any-time per l’ordinamento Efficient Top-k Query Evaluation on Probabilistic Data 24 E se non ci sono domande... grazie per l’attenzione 5 marzo 2008 Efficient Top-k Query Evaluation on Probabilistic Data 25
Scarica
