Informazioni circa le tesine di fine corso

Modalità di esame

Verranno assegnati degli argomenti con materiale bibliografico di partenza sul quale gli studenti dovranno compilare una tesina. E' possibile lavorare in gruppo (non più di 2 persone).

Argomenti

Ecco alcuni esempi di argomenti che si potrebbero trattare (maggiori informazioni su altri argomenti seguiranno):

• PageRank.
  • "PageRank" (titolo preliminare). Francesco Sbordone e Ida Bifulco.
  • Obiettivo: Presentare PageRank, la sua interpretazione analitica e la dimostrazione di correttezza, i meccanismi di interazione di communities ed le tecniche per la promozione di pagine e di comunity.
  • Materiale bibliografico di partenza:
    • "The PageRank Citation Ranking: Bringing Order to the Web", di L. Page, S.  Brin, R. Motwani, T. Winograd, a http://dbpubs.stanford.edu:8090/pub/showDoc.Fulltext?lang=en&doc=1999-66&format=pdf&compression=&name=1999-66.pdf
    • "Inside PageRank" di M.Bianchini, M. Gori e F. Scarselli. ACM Transaction on Internet Technology, Vol.5 No.1, February 2005, Pages 92-128
    • "A survey on Eigenvector Methods for Web Information Retrieval", A. Langville, C.D. Meyer. SIAM Review, Vol.47, No1., pp-135.161
• HITS:
  • Obiettivo: Presentare HITS, la sua interpretazione analitica e la dimostrazione di correttezza, la relazione con PageRank e con le tecniche di cocitation/coreference:
  • Materiale bibliografico di partenza:
    • Kleinberg "Authoritative Sources in a Hyperlinked Environment", Journal of ACM Vol. 46 No. 5, Sept. 1999 http://citeseer.ist.psu.edu/cache/papers/cs/18533/http:zSzzSzwww-dbs.cs.uni-sb.dezSzpublic_htmlzSzlehrezSzprosem00paperszSz1zSzkleinberg-jacm99.pdf/kleinberg99authoritative.pdf
    • C.Ding, X. He, P. Husbands, H.Zha, H.Simon  "PageRank, HITS and a Unified Framework for Link Analysis"  http://www.siam.org/meetings/sdm03/proceedings/sdm03_24.pdf
    • C.Ding, X. He,  H.Zha, H.Simon "Link analysis: Hubs and Authorities on the World Wide Web" Tech rep. 47847, Lawrence Berkeley National Laboratory, Berkeley, CA, 2001
• HTTP:
  • Obiettivo: presentare i principi progettuali di HTTP tramite Representational State Transfer (REST) ed evidenziare le critiche ad alcuni aspetti progettuali ed errori di design che sono adesso evidenti
  • Materiale bibliografico di partenza:
    • J. Mogul. "Claryfying the fundamentals of HTTP", Software, Practice and Experience 2004, vol. 34, pp- 103-134
    •  R.Fielding, R.N. Taylor. "Principled Design of the Modern Web Architecture". ACM Trans. on Internet technology, vol.2, No. 2, May 2002. Pages 115-150.
• Google Cluster
  • Materiale bibliografico di partenza:
    • "Web Search for a Planet: The Google Cluster Architecture", Luiz André Barroso, Jeffrey Dean, Urs Hölzle March 2003, IEEE Micro, Volume 23 Issue 02
    • "Power provisioning for a warehouse-sized computer",   Xiaobo Fan, Wolf-Dietrich Weber, Luiz Andre Barroso. Proceedings of the 34th annual international symposium on Computer architecture, San Diego, California, USA, Pages: 13 - 23, 2007
    • "Failure Trends in a Large Disk Drive Population", Eduardo Pinheiro, Wolf-Dietrich Weber, Luiz André Barroso, 5th USENIX Conference on File and Storage Technologies (FAST 2007), pp. 17-29.
• MapReduce
  • "MapReduce ed applicazioni alla propagazione dei cambiamenti di schema in un DB distribuito" (titolo preliminare). Mario Vacca e Ferdinando Di Martino.
  • "MapReduce e applicazioni in bioinformatica" (titolo preliminare). Gennaro Iaccarino.
• Google File System
  • "Google File System e tecniche per la coerenza temporale nei sistemi distribuiti" (titolo preliminare). Ilaria Manno.
  • Materiale bibliografico di partenza:
    • "The Google File System", Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung.  19th ACM Symposium on Operating Systems Principles, Lake George, NY, October, 2003.
    • Giusto per vedere alcune evoluzioni, "Bigtable: A Distributed Storage System for Structured Data", Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber,  OSDI'06: Seventh Symposium on Operating System Design and Implementation, Seattle, WA, November, 2006.
• Web spamming
  •  Materiale bibliografico di partenza:
    • Come punto di partenza, si può usare Web Spam Taxonomy, by Zoltán Gyöngyi and Hector Garcia-Molina, Proc. of AIRWeb 2005 (usato in parte anche per la lezione) e anche il loro articolo "Spam: it's not just for inboxes anymore",  IEEE Computer Magazine, 200vo.38, No.10). (Il link dovrebbe permettere di scaricare il pdf se accedete dall'università)
    • Hector Garcia-Molina: "Overview of Search Engine Spamming."Web Congress, 2006. LA-Web '06. Fourth Latin American.
    • "Using Spam Farm to Boost PageRank", Ye Du, Yaoyun Shi and Xin Zhao, Proc. of AIRWeb 2007. Identificano la struttura di link farm ottimale per fare spam in PageRank, correggendo (estendendo, dicono loro :-)) un risultato precedente di Zoltan Gyongyi and Hector Garcia-Molina. "Link spam
      alliances". In VLDB '05: Proceedings of the 31st international conference on Very large data bases, pages 517{528. VLDB, 2005.
    • Alcuni lavori interessanti sulle tecniche utilizzate in pratica per fare boosting/hiding, oltre a Web Spam Taxonomy (di AIRWeb 2005):
      • "A Taxonomy of JavaScript Redirection Spam", Kumar Chellapilla and Alexey Maykov,  Proc. of AIRWeb 2007. Presentano le tecniche di obfuscating, che fanno ricaricare pagine via Javascript, in modo che il crawler analizzi una pagina, mentre ne viene visualizzata all'utente una altra.
    • Lavori specialistici si trovano nelle conferenze AIRWeb (Adversarial Information Retrieval on the Web): la prima edizione (2005), la seconda edizione (2006) e la terza edizione(2007).
    • In maniera "politically correct" il web spamming si chiama "Search engine Optimization" (vedete la voce corrispondente su Wikipedia) ed esistono vari siti che trattano di questo (anche a pagamento!) come http://www.seomoz.org (vedete ad esempio una loro survey sugli aspetti più importanti nel ranking a http://www.seomoz.org/article/search-ranking-factors )
    • Circa il tipo di euristiche che vengono applicate, leggete "Google keeps tweaking its search engine", del NYT del 3/6/2007. Un articolo non tecnico ma che fornisce l'idea dell'atmosfera a Google e del tipo di debugging che riescono a fare.
• Struttura del Web:
  • Materiale bibliografico di partenza:
    • Krishna Bharat, Patterns on the Web,  Proceedings of String Processing and Information Retrieval: 10th International Symposium (SPIRE 2003) , pp. 1-15.
    • Solo per qualche dettaglio sulla definizione di Zipf law: "Zipf, Power-laws, and Pareto - a ranking tutorial" di
      Lada A. Adamic disponibile a http://www.hpl.hp.com/research/idl/papers/ranking/ranking.html
    • Per una introduzione ai modelli evolutivi del Web (con un approfondimento tecnico), "A survey of models of the Web graph" di Anthony Bonato
    • Krishna Bharat, Bay-Wei Chang, Monika Henzinger, and Matthias Ruhl, "Who Links to Whom: Mining Linkage between Web Sites", ICDM 2001
    • A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener. Graph structure in the web. 9th International World Wide Web Conference, May 2000.
    • R. Baetza-Yates, B.J.Poblete. Evolution of Web Structure. 12th International World Wide Web Conference, 2003.
    • M. Mitzenmacher, A Brief History of Generative Models for Power Law and Lognormal Distributions, Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.
    • R.Kumar. P. Raghavan, S. Rajagopalan, D.Sivakumar, A.S.Tomkins, E.Upfal. The Web as a graph. Proceedings of the 19th ACM Symposium on Principles of Database Systems (2000), pp. 1-10.
    • Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan and Andrew S. Tomkins. The Web as a graph: measurements, models and methods. Proceedings of the 5th International Computing and combinatorics Conference, 1999 [Citeseer]
    • Applicazioni di power laws, etc. ad altre aree:
      • Economia: la home page di Xavier Gabaix (MIT) contiene vario materiale tra cui una "Zipf's law for cities: an explanation"

Modalità di composizione della tesina

1. Per la compilazione della tesina si richiede l'utilizzo di Latex. Alcune informazioni che possono esservi utili sono riportate di seguito:
• un template per la tesina, con frontespizio, ed esempi vari, è disponibile in TesinaWPATemplate.zip (contiene una guida per le tesi che usano i tesisti del laboratorio Isis, ed alcuni esempi guidati su come usare figure, bibliografia, etc.)
• materiale di aiuto di vario tipo si può trovare in LatexHelp.zip
• Se non avete mai usato Latex, sulle distribuzioni Linux lo trovate di solito installato, mentre per Windows potete scaricare:
  •  Miktex da http://miktex.org/
  • Texnixcenter (open source and free): editor per la facile compilazione e debugging di documenti Latex a http://www.toolscenter.org/
2. Il processo di scrittura della tesina passa attraverso queste fasi:
   1. assegnazione della tesina ad 1 o 2 dottorandi, con materiale bibliografico iniziale (che ha come puro scopo quello di orientare lo studio e che non deve, quindi rappresentare una limitazione all'uso di ulteriore materiale che possiate trovare.. anzi!) (tempo T)
   2. studio preliminare e sottomissione di una bozza di documento (es. indice con una struttura approssimativa e con le fonti bibliografiche che si intende utilizzare) (tempo T+15 giorni)
   3. sottomissione di un draft finale della tesina per la rilettura da parte mia (che richiede 2-3 giorni) (tempo T+30)
   4. versione finale (tempo T+30+3+7)
   Un calendario fissato con delle deadline precise è di aiuto nel concentrare il vostro sforzo in un periodo preciso (in generale non più di un mese e mezzo) e a non disperdere il vostro lavoro in periodo troppo lungo, oltre ad abituarvi a trattare con lavori che hanno scadenze precise. Per questo motivo non saranno garantite "deadline extensions" di nessun tipo.