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 2023/2024 ======

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

    * ** Teacher **: [[http://www.di.unipi.it/~ferragin/|Paolo Ferragina]] and [[https://pages.di.unipi.it/vinciguerra/|Giorgio Vinciguerra]]
    * **Course ID**: 289AA 
    * **CFU:** 6 (first semester)
    * **Language:** English
    * **Question time:** Monday 15-17 by appointment. The meeting will occur via video-conference in the [[https://teams.microsoft.com/l/team/19%3ayx5WDI0x-rp9oz5FUxY40tTWuB1fZOIGfCey3j75hfI1%40thread.tacv2/conversations?groupId=2ff8a6e0-33a0-4bb2-a807-739800a275b2&tenantId=c7456b31-a220-47f5-be52-473828670aa1|virtual room]] of the course.
    * **Official Lecture's Log:** Here it is the [[https://unimap.unipi.it/registri/dettregistriNEW.php?re=10336812::::&ri=9142|registro]].
    * News about this course will be distributed via a [[ https://t.me/+WTDv87SO3_wyNTM0 | 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  | Room C (Polo Fibonacci) | 
| Tuesday  |  11:00 - 13:00  | Room C (Polo Fibonacci) | 



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

The exam will consist of a written test including two parts: **exercises and "oral" questions**. The exam is passed if in both parts the student gets a sufficient score: expressed as the sum of two reported grades.

The first (exercises) and the second (theory questions) parts of the exam can be split into different exam dates, even of different exam sessions. The exam dates are the ones indicated in the calendar on ESAMI. In the case that the second part is not passed or the student abandons the exam, (s)he can keep the rank of the first exam, but this may occur just once. The second time this happens, the rank of the first part is dropped, and the student has to do both parts again.


^ Date  ^ Room  ^ Text ^ Notes |
| 13/11/2023, start at 14:00 | room E | Mid-term exam. {{ :magistraleinformatica:ir:ir23:ir231113.pdf |text}}, {{ :magistraleinformatica:ir:ir23:ir231113-sol1.pdf |solution}}, {{ :magistraleinformatica:ir:ir23:ir231113-ris.pdf |results}} | |
| 15/12/2023, start at 9:00 | room E | Final-term exam. {{ :magistraleinformatica:ir:ir23:ir231215.pdf |text}}, {{ :magistraleinformatica:ir:ir23:ir231215-sol.pdf |solution}}, {{ :magistraleinformatica:ir:ir23: ir231215-ris.pdf |results}}| Students must register at [[https://esami.unipi.it/ |esami.unipi.it]] on the exam date of January and write "final-term" in the notes.  |
| 16/01/2024, start at 9:00 | room C | {{ :magistraleinformatica:ir:ir23:ir240116.pdf |text}}, {{ :magistraleinformatica:ir:ir23:ir240116-sol.pdf |solution}} | |
| 07/02/2024, start at 11:00 | room C | {{ :magistraleinformatica:ir:ir23:ir240207.pdf |text}}, {{ :magistraleinformatica:ir:ir23:ir240207-sol.pdf |solution}} | {{ :magistraleinformatica:ir:ir23:ir240207-res.pdf |Results}}. Students accepting their vote have to send an email to Ferragina, with that statement. Correction occurs on Wednesday, 14th February, at 17:30 in the Teams' room of the course. When you are there, please write on the chat that you are "waiting". |
| 27/05/2024, start at 11:00 | room C | {{ :magistraleinformatica:ir:ir23:ir240527.pdf |text}}, {{ :magistraleinformatica:ir:ir23:ir_solution_27.05.24.pdf |solution}} |  |
| 21/06/2024, start at 11:00 | room C | {{ :magistraleinformatica:ir:ir23:ir240621.pdf |text}}, {{ :magistraleinformatica:ir:ir23:ir_solution_21.06.24.pdf |solution}} |  |
| 11/07/2024, start at 11:00 | room C | {{ :magistraleinformatica:ir:ir23:ir240711.pdf |text}}, {{ :magistraleinformatica:ir:ir23:ir240711-sol.pdf |solution}} |  |
| 04/09/2024, start at 09:00 | room C | {{ :magistraleinformatica:ir:ir23:ir240904.pdf |text}}, {{ :magistraleinformatica:ir:ir23:ir240904-sol.pdf |solution}} |  |

====== 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).
  * If you need to practice with exercises given at previous exams, please look at the [[http://didawiki.di.unipi.it/doku.php/magistraleinformatica/ir/start|pages of the course]] of the previous years, in the section where I list the exam dates, texts, and solutions.

\\

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

[[https://unipiit-my.sharepoint.com/:f:/g/personal/a009142_unipi_it/EpSEv_bfN41Bjuvqrh_aB9EBzBEOnFKd306bQMzluXKVRA?e=1ti0Nf|Video-lectures]] of last year are available at the link and they are linked just for reference if you wish to re-check something you listened in class. This year, lectures are in presence and the program of the course could be different. \\


^ Date         ^ Topics ^ Refs  ^
| 18.09.2023 | Introduction to the course: modern IR, not just search engines! Boolean retrieval model. Matrix document-term. Inverted list: dictionary + postings. How to implement AND, OR, and NOT queries, and their time complexities. | [[https://www.dropbox.com/scl/fi/m562xzrvu0np368bxlc50/Lect-01-introduction.pptx?rlkey=nuelcbjyggp6lq2e629w1aqug&dl=0|Slides]] and sketch of the [[https://www.dropbox.com/scl/fi/6an3yl55wedze0js0mj5j/Lect-01-IR-LAB23-24.pptx?rlkey=pki3hvm9erfky8segq7xsqq17&dl=0|lab activities]]. \\ Chapter 1 of [MRS] |
| 19.09.2023 | Skip pointers, Phrase queries, biword index, and positional index.  | Sect 2.3 and 2.4 of [MRS] |
| 25.09.2023 | Zone indexes. 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. The Bloom filter: definition, time/space complexity, and error bound. | [[https://www.dropbox.com/scl/fi/dqy00wowuvdr0duratjbm/Lect-02-crawling-part-a.pptx?rlkey=rqjqxvhvbqoctvbq1dzuqx7yb&dl=0|Slide1]] and [[https://www.dropbox.com/scl/fi/5y46f14uc7eyrxc48m47l/Lect-03-crawling-part-b.pptx?rlkey=4q85rez6yhz9zbxnajg8fvufj&dl=0|Slide2]].\\ Sections Sections 19.1, 19.2, 19.4, 20.1, 20.2 of [MRS].\\ For doubts on Bloom Filters see [[http://didawiki.di.unipi.it/lib/exe/fetch.php/magistraleinformatica/ir/ir12/reading-bloomfilter.pdf|paper]]. |
| 26.09.2023 | Spectral Bloom Filter: single minimum, recurring minimum, two-level SBF. Consistent Hashing. Web graph compression: properties of the web, power laws, and compressing the adjacency lists.  | Sect 20.3 and 20.4 of [MRS], and this [[https://itnext.io/introducing-consistent-hashing-9a289769052e|page]] and [[http://web.stanford.edu/class/cs168/l/l1.pdf|note]] for consistent hashing. | 
| 03.10.2023 | The issue of hierarchical memories: I/O-model. Index construction: multi-way mergesort, BSBI and SPIMI. Sketch on MapReduce. Distributed indexing: Term-based vs Doc-based partitioning. Dynamic indexing: two indexes, a cascade of indexes (logarithmic method). | [[https://www.dropbox.com/scl/fi/t21itn5m6dxb2zicz8tjp/Lect-06-construction.pptx?rlkey=tvgr33ekdfbbt7ygam2xdemwy&dl=0|Slides]].\\ Chapter 4 of [MRS]. | 
| 09.10.2023 | Locality-sensitive hashing: basics, hamming distance, proof of the probability bounds. Use in an off-line and in an on-line setting. Comparison between LSH and K-means for the clustering problem.  | [[https://www.dropbox.com/scl/fi/ebhfx4wnzo0drhd9fk4qw/Lect-04-LSH-technique-and-dedup.pptx?rlkey=1jxy1knv7a13261rrgz66j0f9&dl=0|Slides]]. | 
| 10.10.2023 | Exact-duplicate documents: Karp-Rabin's rolling hash (with properties and error probability). Near-duplicate documents: Shingling, Jaccard similarity, min-hashing. Min-hashing (with prob property). LSH on integer vectors. Cosine similarity among vectors of real features. | Sect 19.6 of [MRS] | 
| 16.10.2023 | Compressed storage of documents: LZ-based compression. Storage and Transmission of single/group of file(s): Delta compression (Zdelta). | [[https://www.dropbox.com/scl/fi/2w4gdmhvsq7taehdi3t71/Lect-05-compression-docs-and-rsync.ppt?rlkey=kcpwybt09362rin4as09kiiuz&dl=0|Slide]]. |
| 17.10.2023 | File Synchronization (rsync, zsync). Parsing: tokenization, normalization, lemmatization, stemming, thesauri. Statistical properties of texts: Zipf law: classical and generalized, Heaps law, Luhn's consideration. | Sect. 2.1, 2.2 and 5.1.\\ Suggest reading this [[https://www.dropbox.com/s/tsb6j1rmrx3e5zr/Lect%2007%20-%20reading%20-%20rsync%20and%20zsync.pdf?dl=0|paper]] on rsynch and zsync.\\ [[https://www.dropbox.com/scl/fi/aqf4bgpre0i6s4xs0rpa2/Lect-07-parsing-and-text-laws.ppt?rlkey=o2uchcub2vh4v41n13t4o4vyt&dl=0|Slides]] on text parsing. | 
| 18.10.2023 | **Extra lecture (room C, 14 - 16):** Exercises on the topics of the previous lectures | [[https://unipiit.sharepoint.com/sites/a__td_59036/Shared%20Documents/General/Recordings/Extra%20lecture%2018-10-2023-20231018_141709-Meeting%20Recording.mp4?web=1|Video]]. |
| 23.10.2023 | Exercises. LSH for cosine similarity estimation.  |  |
| 24.10.2023 | Soft AND, Caching, and Tiered index. Keyword extraction: statistical, chi-square test. Rake tool. Query processing: soft-AND. Exact search: hashing. Prefix search: compacted trie, front coding, 2-level indexing. | Sect. 5.2 of [MRS].\\ [[https://www.dropbox.com/scl/fi/jqocyz8249chp5ofcd9cy/Lect-08-dict-search.pptx?rlkey=5ybx0t33rdhbw2w52m2quzaiu&dl=0|Slides]]. |
| 30.10.2023 | Edit distance with e-errors via brute-force approach, or Dynamic Programming (possibly weighted). Overlap measure with k-gram index. An index for e-error matches based on k-gram index (with false positives, no false negatives). Phonetic match.  |   |
| 31.10.2023 | Wild-card queries: Permuterm. Scoring of the candidates. | |
| 06.11.2023 | Posting list compression, codes: gamma, variable bytes (t-nibble), Simple9, Group varint.  | Sect. 5.3 of [MRS]. \\ [[https://www.dropbox.com/s/sd6a5fiosjxa2em/Lect%2009%20-%20compression%20integers%20%28new%29.ppt?dl=0|Slides]].\\ [[https://unipiit.sharepoint.com/sites/a__td_59036/Shared%20Documents/General/Recordings/Lecture%206-11-23-20231106_110822-Meeting%20Recording.mp4?web=1|Video]] | 
| 07.11.2023 | Exercises | |
| 13.11.2023 | **MIDTERM exam:** 14-16 in room E | You have to register [[https://forms.office.com/e/L9ypGq7Rk0|here]] by 8 november 2023. |
| 14.11.2023 | Posting list compression: PForDelta, Elias-Fano.\\ Text-based ranking: dice, jaccard, tf-idf. | Sect 6.2 of [MRS]. \\ {{ :magistraleinformatica:ir:ir23:lect_12-text_ranking.ppt | Slides }} |
| 20.11.2023 | Vector space model and cosine similarity doc-doc and query-doc. Storage of tf-idf and use for computing document-query similarity. Fast top-k retrieval: many query terms, high idf, champion lists, fancy hits, clustering. | Sect 6.3 and 7 of [MRS] |
| 21.11.2023 | Exact Top-K: WAND and blocked-WAND. |  |
| 27.11.2023 | Relevance feedback, Rocchio, pseudo-relevance feedback, query expansion. Performance measures: precision, recall, F1, DCG and NDCG. Exercise on (Blocked) WAND. | Sect 8.1-8.3 and 9 [MRS]. |
| 28.11.2023 | Random Walks. Link-based ranking: PageRank. | Sect 21.1 and 21.2 of [MRS]. \\ {{ :magistraleinformatica:ir:ir23:lect_13-web_ranking.pptx |Slides}}. |
| 04.12.2023 | Topic-specific PageRank. Personalized PageRank. HITS. Application to Text Summarization. Exercise on PageRank.  | Sect 21.2.3 and 21.3 of [MRS]. |
| 05.12.2023 | Projections to smaller spaces: Latent Semantic Indexing (LSI). Exercise on TF-IDF. | Chapter 18 of [MRS].\\ [[https://www.dropbox.com/s/rxd4p3qv60cnuuw/lect%2015%20-%20LSI%20and%20random%20proj%20%28breve%29.ppt?dl=0|Slides]]. |
| 11.12.2023 | **Extra lecture (11-13, room C)**: Exercises on posting list compression, Personalized PageRank, WAND and Blocked WAND. Lab on Entity linkers: TagMe. | {{ :magistraleinformatica:ir:ir23:ir-lab23-24-annotators.pptx |Slides}}. |
| 12.12.2023 | **Extra lecture (11-13, room C)**: Lab on ElasticSearch, please bring your own laptop and make sure you have a working installation of a recent version of Python and [[https://www.anaconda.com/products/distribution|Anaconda]]. Use them to create a clean environment specific for this course. The only required package is ElasticSearch: install it via ''pip install elasticsearch==7.14.0''. All material of the lecture is in this [[https://github.com/LorenzoBellomo/InformationRetrievalLab2023|repo]] | {{ :magistraleinformatica:ir:ir23:ir-lab23-24-indexing.pptx |Slides}}. |
| 15.12.2023 | **Final-term exam (9-11, room E)** | |