DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Advanced Algorithms for Massive Datasets @ BISS2010 ======

**Teacher:** Paolo Ferragina ([[http://www.di.unipi.it/~ferragin|home]], [[mailto:ferragina@di.unipi.it|email]])

**Period:** Second week of March 2010 

===== Summary =====

This is the course I teached during March 2010 at the [[http://www.bici.eu/biss2010/index.html|Bertinoro International Spring School]] for PhD students in Computer Science and Engineering. The main goal of the course was to address the new algorithmic challenges posed by the processing of massive data occurring in modern information retrieval and data mining applications, and dictated by the architectural features of the memory hierarchy of current computers. These issues force algorithm designers to address simultaneously data compression (fitting more data in the faster/smaller memory levels) and cache-friendly data access (exploiting the accessing features of memory levels). 

Every lecture will follow a problem-driven approach that starts from a real software-design problem, abstracts it in a combinatorial way (suitable for an algorithmic investigation), and then introduces basic and sophisticated algorithmic solutions aimed at minimizing the use of computational resources like time, space, communication, I/O, energy consumption, etc.. The theoretical investigation will go hand-in-hand with some algorithm-engineering considerations. 
===== Lectures: topics and material =====

**Lecture 1.** Introduction to (Modern) Computational Models. Sorting vs Permuting. [{{:biss2010:ferragina-biss-day1.zip|slides}}, {{:biss2010:lect1-sorting.zip|material}}]

**Lecture 2.** Hashing: Uniform, Universal, Perfect, Cuckoo. [{{:biss2010:ferragina-biss-day2a.zip|slides}}, {{:biss2010:lect2-hash.zip|material}}]

**Lecture 3.** Dictionaries: From arrays to (Patricia) tries and Bloom Filters, from plain storage to (Locality Preserving) Front Coding. [{{:biss2010:ferragina-biss-day3.zip|slides}}, {{:biss2010:lect3-trie.zip|material}}]

**Lecture 4.** Text indexing and mining: suffix trees and arrays. Some mining queries, and the issue "LCA=RMQ". [{{:biss2010:ferragina-biss-day4.zip|slides}}, {{:biss2010:lect4-suffixtreesuffixarray.zip|material}}]

**Lecture 5.** Data compression: basics, Huffman, Arithmetic, bzip2 and beyond. [{{:biss2010:ferragina-biss-day5.zip|slides}}, {{:biss2010:lect5-compression.zip|material}}]

===== Exam =====

The exam consists either in the solution of a bunch of exercises, or in the attack of one of the software project listed below. Each project can be conducted in team (no more than 3 students), and should be preferably close to the research interest of the candidate. 

The students willing to give the exam should send me an [[mailto:ferragina@di.unipi.it|email]] with subject [BISS09], specifying the chosen subject for the work, and the list of participants in the team. Once negotiated, the assigned teamwork will be inserted in this wiki. The exam must be completed within 2010. 
===== List of Projects =====

  * Suggester for typing [inspiring papers? {{:biss2010:paperchato.pdf|one}}, {{:biss2010:article.zip|two}}]
  * Problem posed by Chakrabharti [inspiring papers? {{:biss2010:chakrabhartisearch1.pdf|one}}, {{:biss2010:chakrabhartisearch2.pdf|two}}] 
  * Permuting Web pages to improve compression ratio [inspiring papers? {{:biss2010:wsdm022-ferragina.pdf|one}}, {{:biss2010:clusteringtext.pdf|two}}, {{:biss2010:suelwww2010reorder.pdf|three}}, {{:biss2010:ferraginawebcompression.tgz|software}}, [[http://brie.di.unipi.it/_UKOriginal1Gb.warc.bz2|UK-crawl]], [[http://brie.di.unipi.it/_UKURLsorted1Gb.warc.bz2|UK-URLsort]]]
  * Generalised BWT [inspiring papers? {{:biss2010:generalisedbwt.pdf|one}}, [[http://people.unipmn.it/manzini/bwtdisk/|sparring partner]], [[http://brie.di.unipi.it/_UKOriginal1Gb.warc.bz2|UK-crawl]],]
  * Temporal data mining on a DB of cars [ [[http://brie.di.unipi.it/autoscout24.tgz|dataset]] ]
DidaWiki

Strumenti Utente

Strumenti Sito

Strumenti Pagina
