Introduzione al corso
Organizzazione record e file
Alberi B, hash in memoria secondaria
Indici invertiti
Basi di dati di documenti e DL
Esercitazioni
Document Engineering
Datawarehouse e DataMining
Ottimizzazione query
(B) H.Garcia-Molina, J.D. Ullman, J. Widom. Database systems the complete book. Prentice-Hall International - 2002
(I) C.D. Manning, P. Raghavan, P. Raghavan Introduction to Information Retrieval, Cambridge University Press - 2008
(B) I. Witten, A. Moffat, T.C. Bell Managing Gigabytes, Van Nostrand Reinhold – 1999
(I) W. Y. Arms Digital Libraries, MIT press - 2000
(B) M Lesk, Understanding Digital Libraries Mk
(I) A. Rajaraman, J. D. Ullman, Mining of Massive Datasets, 2011
Nota:
(B) indica che il libro è presente nella biblioteca di S. Marta
(I) indica un libro scaricabile da Internet
Materiale reso disponibile agli studenti tramite il sito
e-l.unifi.it
Obiettivi Formativi
L’obiettivo del corso è di fornire conoscenze sulla tecnologia delle Basi di Dati e sulle principali applicazioni emergenti.
Al termine del corso sarà possibile analizzare criticamente e
sviluppare algoritmi e metodi per la gestione efficiente di
grandi quantità di informazioni.
Prerequisiti
Nozioni apprese nei corsi di primo livello di Basi di Dati e Fondamenti di Informatica II.
Metodi Didattici
Lezioni frontali, esercitazioni in classe, svolgimento assistito
di elaborati
Altre Informazioni
Appelli Esame 2012/2013 Tecnologia delle Basi di Dati
Gli esami orali vengono svolti nell'ufficio del docente, dopo aver concluso l'elaborato.
Modalità di verifica apprendimento
Studio e presentazione di articolo (lavoro individuale) 15 %
Elaborato (gruppi di 2 persone) 65 %
Orale (individuale) su argomenti selezionati 20 %
Programma del corso
1. Introduzione (A11.1, A11.2; C1 )
(a) Architettura di un DBMS
(b) Altri "tipi" di basi di dati
(c) Il ruolo dell'informazione testuale
2. Hardware (A11.3, A11.4, A11.5; C2; H2.1 H2.2)
(a) Caratteristiche dispositivi di memorizzazione secondaria: tracce, settori, controllore del
disco, tempi di accesso (random, sequenziale)
(b) Ottimizzazioni, esempio doppio buffer, dimensioni blocco
(c) Algoritmo di merge-sort in memoria secondaria; two-phase e multi-phase multiway merge-
sort
(d) File system distribuiti. Paradigma Map-Reduce, architettura hw e sw, coordinazione esecuzione
(e) Esempio: word count con Map-Reduce
3. Gestione della memoria permanente (A12)
(a) Rappresentazione di dati elementari, il caso particolare delle stringhe di caratteri; Tipi di record (formati fisso vs variabile; lunghezza fissa vs variabile; formati ibridi)
(b) Caratteristiche blocchi in memoria secondaria (separazione blocchi, record su pi ù blocchi,
record misti, suddivisione record, organizzazione, indirizzamento)
(c) I file; allocazione blocchi in fi le; Operazioni su file (un record alla volta VS un insieme alla volta); Opzioni per cancellare record
(d) Gestione dei bu ffer
4. Indicizzazione di dati (A13.1, A13.2; C3,C6)
(a) Tipi di indice e loro confronto
(b) Organizzazione seriale e sequenziale
(c) Indici densi e sparsi, indici multilivello
(d) Gestione chiavi duplicate con i vari tipi di indice
(e) Inserimento e cancellazione con i vari tipi di indice
(f) Attributi non chiave (indici secondari); gestione valori duplicati; bucket
5. Alberi di ricerca in memoria secondaria (A13.3; C5)
(a) Paginazione di alberi binari di ricerca
(b) Alberi B+: struttura, operazioni, dimensione nodi, propriet à, scelta dimensione pagina
(c) Alberi B
(d) Dimensioni strutture dati: indici con alberi B+ (densi o sparsi) combinati con le seriali o
sequenziali
7. Chiavi di accesso multiple (A14.1, A14.2, A14.3; C7)
(a) Applicazioni (geogra che, data-mining, elaborazione immagini); curse of dimensionality
(b) Tipi di query multidimensionali
(c) Implementazione in SQL e uso di indici monodimensionali; il caso della query NN
(d) Organizzazione ad albero: R-tree (struttura, operazioni), Quad-tree (struttura, operazioni),
KD-tree (struttura, operazioni, organizzazione in memoria secondaria), spazio occupato da
nodi in varie organizzazioni
(e) Organizzazioni "hash-like": Grid fi le (ricerca, inserimento, memorizzazione su disco), Partitioned hash table, Confronto tra metodi
8. Indici invertiti (B1, B2, B4; D5)
(a) Applicazioni per Information Retrieval (IR), dalle concordanze agli indici invertiti; Termini indice; Architettura sistemi IR; ad-hoc retrieval VS fi ltering
(b) Modelli IR e loro implementazione. Astrazione "bag of words", Modello booleano, Modello
dello spazio vettoriale, Pesatura TF-IDF, Modello booleano esteso e sue estensioni, Modello
vettoriale generalizzato
(c) Strutture dati per indice invertito. Dizionario con hash, alberi, trie. Liste di posting con matrici, liste collegate, serializzazione su disco. Costruzione indice invertito; pre-elaborazione linguistica (tekenization, stemming, stop-word).
(d) Metodi per costruire indici invertiti: organizzazione in memoria centrale, BSBI, SPIMI,
Indicizzamento distribuito, Indirizzamento dinamico
(e) Ottimizzazioni per interrogazioni booleane
(f) Etichettatura e stemming
9. Compressione indice invertito (B5; D3)
(a) Compressione dei puntatori: puntatori di salto, codi ca unaria; codici gamma e delta , analisi
prestazioni basata su legge di Zipf
(b) Compressione del dizionario: compressione dei termini; riduzione delle parole indicizzate;
codi ca frontale
10. Esecuzione Query IR (B3, B6, B7; D4)
(a) Query booleane (vettore occorrenze, liste di posting, fusioni di liste di posting, ottimizzazione query)
(b) Query e scoring in spazi vettoriali (tf-idf, calcolo del coseno, ranking e ciente, calcolo del singolo coseno)
(c) Filtratura documenti rilevanti, punteggi basati su autorevolezza,indici a strati, impiego di
cluster, Latent Semantic Indexing
(d) Dati strutturati e non-strutturati. Metadati, Query con combinazioni di zone. Indici di
zone. Query strutturali
(e) Query di frasi. Indici di coppie di parole, indici posizionali e loro dimensioni, indici su frasi (frasi pi ù comuni, nextword).
(f) Interrogazioni con wild-card (indice permutato, indice di bi-gram e n-gram)
(g) Correzione ortografi ca: correzione di documenti e parole isolate, edit distance, n-gram
overlap.
(h) Valutazioni sistemi ranked e un-ranked: Precision, Recall, Falsi/Veri Positivi/Negativi, F
measure, curve PR, rank precision
(i) Tutorial Lucene
11. Analisi di immagini di documenti (I,J + Lucidi + Articoli in "Applicazioni")
(a) Applicazioni, contenuto fi sico e logico, ordine delle operazioni
(b) Acquisizione e memorizzazione, compressione immagini di documenti
(c) Pre-processing: filtraggio, binarizzazione, eliminazione rumore, image continuation
(d) Segmentazione oggetti
(e) Estrazione e analisi di contorni
(f) Componenti connesse, algoritmi iterativi e ricorsivi
(g) Operazioni morfologiche di base, localizzazione parole
(h) Ruling lines, segmentazione parole manoscritte
(i) Skew detection, dewarping, thinning
(j) Analisi del layout: RLSA, docstrum, Area Voronoi Diagram, profi lo delle proiezioni, XY-
tree
(k) Apprendimento automatico per analisi del layout: pixel classifi cation, zone classi fication,
cc classifi cation, region classi fication (J)
(l) Page classi fication/retrieval. Descrizioni pagine: globali, basate su liste, strutturali,
(m) Riconoscimento testo. on-line vs o -line, Optical Character Recognition, riconoscimento di
caratteri manoscritti: segmentazione, pre-processing, rappresentazione.
12. Document Image Retrieval (D2+K)
(a) Information retrieval in biblioteche
(b) Document image retrieval basato sul riconoscimento
(c) Document image retrival senza riconoscimento
(d) Recupero sulla base del layout o del contenuto testuale, clustering di parole e pagine
13. Biblioteche digitali (E; F1, F2, F3, F5, F7, F9, F12)
(a) Biblioteche digitali e tradizionali
(b) Metadati: bibtex, Dublin Core, RDF
(c) Gathering: Z39.50, OAI-PMH
(d) Esempi di Biblioteche Digitali
(e) Progetti di digitalizzazione, gestione copyright
(f) Digital Preservation, scelta dei formati
(g) Software open-source per DL: greenstone, DSPACE
14. Document Engineering (G + L4+ Lucidi (e fonti citate nei lucidi))
(a) Tipi di documenti: documenti data-centric VS document-centric
(b) Formati documenti testuali: insiemi di caratteri, UNICODE, formati testuali
(c) XML, de finire strutture in XML, XML vs HTML, SGML, presentation markup e structural
markup in editoria elettronica
(d) Processare XML: SAX, Dom, XSLT, CSS, XSL:FO
(e) XML retrieval, XPath, XQuery, SQL/XNL, FLWOR. DB nativi XML, DB2 pureXML (B10)
(f) Linguaggi di descrizione di pagina: SVG, PostScript, PDF: tool e struttura fi le
(g) Dispositivi di lettura/scrittura Ebook-reader, tecnologia touch-screen
(h) Formati per ebook: ePub (OCF, OPF, OPS). File ODT. Gestione/conversione file ePub
(i) Analisi di immagini di documenti ed Ebook
15. Data warehouse (A20)
(a) Warehouse, OLTP vs OLAP
(b) Modelli dati e operatori. Stelle, occhi di neve. Slice and dice, roll-up, drill-down. Data
cube. Rolap e molap
(c) Implementazione di un warehouse: monitoraggio, integrazione, elaborazione, gestione
(d) Data mining, esempi di utilizzo di alberi di decisione e clustering
(e) Modello market-basket. Frequent itemset
(f) Regole di associazione
(g) Algoritmo A-priori. Implementazione e ciente: matrice triangolare, matrice sparsa, uti-
lizzo e ciente memoria centralem, algoritmo PCY
(h) Web data mining (B19, B20, B21)
(i) Caratteristiche web, analisi di link (HITS, pagerank)
(j) Motori di ricerca: crawler, analisi di pagine, indicizzamento
16. Applicazioni (EL)
(a) Analisi e discussione (in classe) di articoli scientifi ci
i. Analisi tabelle
ii. Analisi layout
iii. Testo manoscritto
iv. Identi cazione scrittore
v. Riconoscimento simboli
(b) Elaborato
Bibliografi a
A) H.Garcia-Molina, J.D. Ullman, J. Widom. Database systems the complete book. Prentice-Hall
International - 2002 (L)
B) C.D. Manning, P. Raghavan, P. Raghavan Introduction to Information Retrieval, Cambridge
University Press - 2008 (I)
C) A. Albano. Costruire sistemi per basi di dati, Addison Wesley - 2001 (L)
D) I. Witten, A. Mo at, T.C. Bell Managing Gigabytes, Van Nostrand Reinhold, 1999 (L)
E) W. Y. Arms Digital Libraries, MIT press - 2000 (I)
F) M Lesk, Understanding Digital Libraries Mk (L)
G) R.J. Glushko, A.T. McGrath, Document Engineering, MIT press 2005
H) A. Rajaraman, J. Leskovec, J. D. Ullman, Mining of Massive Datasets (I)
I) S. Marinai, Introduction to Document Analysis and Recognition, Studies in Computational
Intelligence (SCI) 90, 120 (2008), Springer-Verlag Berlin Heidelberg 2008 (I)
J) S. Marinai, Learning Algorithms for Document Layout Analysis pp. 400-419 Handbook of
Statistics and Machine Learning: Theory and Applications Volume 31, 2013(EL)
K) S. Marinai. A survey of document image retrieval in digital libraries. 9th Colloque International
Francophone sur l'Ecrit et le Document (CIFED 2006), pag. 193-198. (I)
L) I. H. Witten, D. Bainbridge and D. M. Nichols, How to build a digital library / Morgan Kauf-
mann, 2010 (L)
Nota: (L) indica che il libro e disponibile in biblioteca a S. Marta; (I) indica che il libro pu o essere scaricato da Internet; (EL) indica che pu o essere scaricato dal sito di E-L.