DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Information Retrieval - Academic Year 2019/2020 ======

====== General Information ======

    * ** Teacher **: [[http://www.di.unipi.it/~ferragin/|Paolo Ferragina]]
    * **Course ID**: 289AA 
    * **CFU:** 6 (first semester)
    * **Language:** English
    * **Question time:** Monday 15-17, or appointment
    * **Official Lecture's Log:** Here it is the [[https://unimap.unipi.it/registri/dettregistriNEW.php?re=3297562::::&ri=9142| registro]].
    * News about this course will be distributed via a [[ https://t.me/CourseIR2019 | Telegram channel]]

\\

====== Goals ======

Study, design and analysis of IR systems which are efficient and effective to process, mine, search, cluster and classify documents, coming from textual as well as any unstructured domain. In the lectures, we will:

     * study and analyze the main components of a modern search engine: Crawler, Parser, Compressor, Indexer, Query resolver, Query and Document annotator, Results Ranker; 

     * dig into some basic algorithmic techniques which are now ubiquitous in any IR application for data compression, indexing and sketching;

     * describe few other IR tools which are used either as a component of a search engine or as independent tools and build up the previous algorithmic techniques, such as: Classification, Clustering, Recommendation, Random Sampling, Locality Sensitive Hashing. 

\\

====== Schedule of the Lectures ======

^           Week Schedule           ^^^
^  Day  ^  Time Slot  ^  Room  ^
| Monday  |  11:00 - 13:00  |  L1  | 
| Tuesday  |  9:00 - 11:00  |  L1  | 

\\

====== Exams ======

The exam will consist of a written test plus an oral discussion on the exercises. 

^ Date         ^ Room ^ Text ^ Notes |
| 26/11/19, 9:00-11:00 | First Midterm exam | {{ :magistraleinformatica:ir:ir19:ir191126.docx |text}}, {{ :magistraleinformatica:ir:ir19:informationretrieval-1920_primo_compitino_.pdf |results}}, {{ :magistraleinformatica:ir:ir19:soluzione_ir_nov_2019_.pdf |solution}} | Students that got a rank >= 16 can participate to the second midterm exam. To the average of the two midterms will be added +2. |
| 16/12/19, 11:00-13:00 | FinalTerm | {{ :magistraleinformatica:ir:ir19:ir191216.docx |text}}, {{ :magistraleinformatica:ir:ir19:soluzione_copitino_2_ir.pdf |solution}}, {{ :magistraleinformatica:ir:ir19:informationretrieval-1920_compitino_2_.pdf |results}}. | Score “30 e lode” has been assigned only to the students who got rank 32 (I used ceiling and not floor of the average, and summed 2!). **Corrections will be shown** in my office, Thursday 9th January at 9:00. The score is lost if the student participates to one of the next exams (just sitting is enough !). The score can be **registered in any of the following exam dates** (in the summer, too), but PLEASE do not write your name in the ESAMI platform if you want to register your exam score, just show yourself in one of those dates. |
| 13/01/20, 14:00-17:00 | room on exam's site | {{ :magistraleinformatica:ir:ir19:ir200113.docx |text}}, {{ :magistraleinformatica:ir:ir19:soluzione_ir_13-1-2020_1.pdf |solution}}. | The score is lost if the student participates to one of the next exams (just sitting is enough !). The score can be registered in any of the following exam dates (even in the summer), but PLEASE do not write your name in the ESAMI platform if you want to register your exam score, just show yourself in one of those dates. |
| 10/02/20, 14:00-17:00 | room on exam's site | {{ :magistraleinformatica:ir:ir19:ir200210.docx |text}}, {{ :magistraleinformatica:ir:ir19:soluzione_ir_10-2-2020.pdf |solution}}. | The score is lost if the student participates to one of the next exams (just sitting is enough !). The score can be registered in any of the following exam dates (even in the summer), but PLEASE do not write your name in the ESAMI platform if you want to register your exam score, just show yourself in one of those dates. |
| 15/06/20, 9:00- | virtual room on Teams | {{ :magistraleinformatica:ir:ir19:ir200615.pdf |pre-test}} to be admitted to the oral. | The score is lost if the student participates to one of the next exams (just sitting is enough !). The score can be registered in any of the following exam dates (even in the summer), but PLEASE do not write your name in the ESAMI platform if you want to register your exam score, just show yourself in one of those dates. |
| 13/07/20, 9:00- | virtual room on Teams | pre-test to be admitted to the oral. | The score is lost if the student participates to one of the next exams (just sitting is enough !). The score can be registered in any of the following exam dates (even in the summer), but PLEASE do not write your name in the ESAMI platform if you want to register your exam score, just show yourself in one of those dates. |

====== Materials for study ======

  * **[MRS]** C.D. Manning, P. Raghavan, H. Schutze. //Introduction to Information Retrieval//. Cambridge University Press, 2008. [ [[http://nlp.stanford.edu/IR-book/information-retrieval-book.html| link]] ]
  * Some copies of papers or notes (linked below).

\\

====== Lectures ======

^ Date         ^ Argument ^ Refs  ^
| 16.09.2019 | Introduction to the course: modern IR, not just search engines! Boolean retrieval model. Matrix document-term. Inverted list: dictionary + postings. How to implement an AND, OR and NOT queries, and their time complexities. | {{ :magistraleinformatica:ir:ir19:lect_01-introduction.ppt |Slides}}.\\ Chapter 1 of [MRS] |
| 17.09.2018 | Web search engine: its structure, difficulties in their design and their epochs. The Web graph: some useful structural properties (such as Bow Tie). Crawling: problems and algorithmic structure. An example: Mercator.  | {{ :magistraleinformatica:ir:ir19:lect_02-crawling_part_a_.ppt |Slides}}.\\ Sections 19.1, 19.2, 19.4, 20.1, 20.2 of [MRS]. |
| 23.09.2019 | Few useful algorithmic techniques for crawling the Web (and not only that!): Bloom Filter and Spectral Bloom Filter. Some other uses of Bloom Filter. | {{ :magistraleinformatica:ir:ir19:lect_03-crawling_part_b_.ppt |Slides}}. For doubts on Bloom Filter see {{:magistraleinformatica:ir:ir12:reading-bloomfilter.pdf|paper}}. |
| 24.09.2019 | Other useful algorithmic techniques for crawling the Web (and not only that!): Consistent Hashing. | Slides of the previous lecture.\\ Sect 19.1 and 19.2 of [MRS]. |
| 30.09.2019 | Locality-sensitive hashing: basics, hamming distance, proof of the probability bounds. | {{ :magistraleinformatica:ir:ir19:lect_04-lsh_technique.ppt |Slides}} | 
| 01.10.2019 | Exact-duplicate documents: Karp-Rabin's rolling hash (with properties and error probability). Near-duplicate documents: Shingling, Jaccard similarity, min-hashing (with prob property), LSH on integer vectors, cosine-similarity among vectors of real-features. | {{ :magistraleinformatica:ir:ir19:lect_05-deduplication.ppt |Slides}}. \\ Sect 19.6 of [MRS] | 
| 07.10.2019 | Web graph properties and its compressed storage. The issue of hierarchical memories: I/O-model. Index construction: multi-way mergesort, BSBI and SPIMI. | Slides on WebGraph are at the end of slides of 23.09.\\ {{ :magistraleinformatica:ir:ir19:lect_06-construction.ppt |Slides this lecture}}.\\ Sect 20.3 and 20.4 of [MRS]. Chapter 4 of [MRS] | 
| 08.10.2019 | Sketch on MapReduce. Distributed indexing: Term-based vs Doc-based partitioning. Dynamic indexing: two indexes, a cascade of indexes. Compressed storage of documents: LZ-based compression. | {{ :magistraleinformatica:ir:ir19:lect_07-compression_docs_and_rsync.ppt |Slides}}. \\ Chapter 4 of [MRS]. | 
| 14.10.2019 | Storage and Transmission of single/group of file(s): Delta compression (Zdelta), File Synchronization (rsync, zsync), and File Reconciliation. | Reading a [[https://www.dropbox.com/s/tsb6j1rmrx3e5zr/Lect%2007%20-%20reading%20-%20rsync%20and%20zsync.pdf?dl=0|paper]]. | 
| 15.10.2019 | Parsing: tokenization, normalization, lemmatization, stemming, thesauri. Statistical properties of texts: Zipf law: classical and generalized, Heaps law, Luhn's consideration. Keyword extraction: statistical, chi-square test, Rake tool. | {{ :magistraleinformatica:ir:ir19:lect_08-parsing_and_text_laws.ppt |Slides}}.\\ Sect. 2.1, 2.2 and 5.1 of [MRS]. |
| 21.10.2019 | Exact search: hashing. Prefix search: compacted trie, front coding, 2-level indexing. | {{ :magistraleinformatica:ir:ir19:lect_09-dict_search.ppt |Slide}}. |
| 22.10.2019 | Edit distance via brute-force approach, or Dynamic Programming (possibly weighted). Overlap measure with k-gram index. Edit distance with k-gram index. One-error match. Wild-card queries (permuterm, k-gram). Phonetic match. Context-sensitive match. | Chap 3 of [MRS].  |
| 28.10.2019 | Exercises | |
| 29.10.2019 | Seminar on Sports Analytics | by Luca Pappalardo, [[https://drive.google.com/file/d/1x7tAhz__nav5vW-49uFaojiXuTDRR7Jz/view | slides]] |
| 04.11.2019 | Exercises | |
| 05.11.2019 | Query processing: soft-AND, skip pointers, caching, phrase queries. Tiered index. Posting list compression, codes: gamma, variable bytes (t-nibble), PForDelta and Elias-Fano. | Sect. 2.3 and 2.4 and 5.3 of [MRS] and {{:magistraleinformaticanetworking/ae/ae2014/chap_9.pdf|Ferragina's notes}} (only the coders presented in class). {{ :magistraleinformatica:ir:ir19:lect_10-query_resolver.ppt |Slides}} and {{ :magistraleinformatica:ir:ir19:lect_11_-_compression_integers.ppt |Slides}}. | 
| 18.11.2019 | Cancellata per allerta meteo | | 
| 19.11.2019 | Text-based ranking: dice, jaccard, tf-idf. Vector space model. Storage of tf-idf and use for computing document-query similarity. Fast top-k retrieval: high idf, champion lists, many query-terms, fancy hits, clustering.  | Sect 6.2 and 6.3 and 7 from [MRS]. {{ :magistraleinformatica:ir:ir19:lect_13-text_ranking.ppt |Slides.}}|  
| 25.11.2019 | Exact Top-K: WAND and blocked-WAND. Relevance feedback, Rocchio, pseudo-relevance feedback, query expansion. Performance measures: precision, recall, F1 and user happiness. | Chap 8 and 9 of [MRS] |   
| 26.11.2019 | First MidTerm exam | |
| 02.12.2019 | Random Walks. Link-based ranking: pagerank, topic-based pagerank, personalized pagerank, HITS. | Chap 21 of [MRS]. {{ :magistraleinformatica:ir:ir19:lect_14-web_ranking.ppt |Slides}} |
| 03.12.2019 | Projections to smaller spaces: Latent Semantic Indexing (LSI). Random Projections: Johnson-Linderstauss Lemma and its applications.  | Chap 18 from [MRS]. {{ :magistraleinformatica:ir:ir19:lect_15-lsi_and_random_proj.ppt |Slides}}. |  
| 05.12.2019 | Semantic-annotation tools: basics, Wikipedia structure, TAGME and other annotators. Various approaches to text representation and their applications. An example of a sophisticate system: Wiser.  | Slides {{ :magistraleinformatica:ir:ir19:lect_16-topic_annotators_breve_.pptx |tagme}} and {{ :magistraleinformatica:ir:ir19:lect_16_-_wiser.pptx |wiser}}. |
| 09.12.2019 | Canceled | |
| 10.12.2019 | Canceled | |
| 12.12.2019 | Exercises on the second part of the course | |
| 13.12.2019 | Exercises on the second part of the course | |
| 16.12.2019 | Second MidTerm exam | |
| 17.12.2019 | Canceled | |

\\
\\
DidaWiki

Strumenti Utente

Strumenti Sito

Strumenti Pagina
