Princeton University Computer Science Dept.

Computer Science 435 Information Retrieval, Discovery, and Delivery Andrea LaPaugh

Spring 2008

• Class presentation now on line as pdf.
• Reading:
  • Bush, Vannevar,  As We May Think,  Atlantic Monthly,  July 1945.  (The famous memex paper.)
  • Introduction to Information Retrieval, Preface and Chapter 1, Introduction and sections 1.1, 1.4, 1.5.
    
  
  

• Class presentation now on line as pdf
• Reading, either of:
•  Introduction to Information Retrieval, Chapter 6: Introduction and sections 6.2 and 6.3.
• Note: Introduction to Information Retrieval discusses building indexes for document collections before it discusses models of documents and queries.  Therefore, we are reading later chapters first.  Please don't worry about the exact content of the index for now.  If you prefer to read a text that treats the topic in the same order as we are going to, you can read the chapters assigned below in Modern Information Retrieval instead.
• *Modern Information Retrieval Chapter 1, section 1.4;  Chapter 2 sections 2.1-2.4 and 2.5.1 - 2.5.3.

• Class presentation now on line as pdf
• Reading:  continue with material from Feb. 6.

• Class presentation now on line as pdf
• Reading:
• Introduction to Information Retrieval,  Chapter 6: sections 6.4.1, 6.4.2, 6.4.3.
• Introduction to Information Retrieval  Chapter 18 (note that section 18.1 is helpful background but not absolutely necessary).
• Assignment 1 due Wed. February 20.

• Powerpoint presentation on Latent Semantic Indexing - pdf file:  (Includes summary of Latent Semantic Indexing posted earlier.)
• Of interest: 
• References to Papers on LSI from Telcordia Technologies, where LSI was first developed.  Includes link to Deerwester, Dumais et. al.
  

• Class presentation on extended model (pdf).
  
• Summary of PageRank
  
• Assignment 1 due today.
• Reading (originally for Feb. 18):
• Introduction to Information Retrieval, Chapter 19, Introduction, Sections 1-4.
• Introduction to Information Retrieval, Chapter 21.
• Also of interest, original papers:
• (HITS algorithm) Kleinberg, Jon, Authoritative sources in a hyperlinked environment, Journal of the ACM, Vol. 46, No. 5(Sept. 1999), pp.604-632.  (Earlier versions appeared in Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998 and as  IBM Research Report RJ 10076, May 1997.)
• (PageRank algorithm) Page, Larry and Sergey Brin, R. Motwani, T. Winograd, The PageRank Citation Ranking: Bringing Order to the Web,  Stanford Digital Library Technologies Project TR, Jan. 1998.  (Early version:  L. Page. PageRank: Bringing order to the web. Stanford Digital Libraries Working Paper 1997-0072, Stanford University, 1997. )

• Class presentation on link-based ranking (pdf).

• Class presentation on evaluation of retrieval systems (pdf).
• Reading (originally for Feb. 25):
• Introduction to Information Retrieval, Chapter 8

• Class presentation on query evaluation and data structure for index (pdf).
• Reading (originally for Feb. 27)
  
• Introduction to Information Retrieval, Chapter 1, Sections 2 and 3.
• Introduction to Information Retrieval, Chapter 2
• Introduction to Information Retrieval, Chapter 3, Introduction and Section 1.

• Class presentation on index construction (pdf).   (Small update 3/7.)
  
• Reading
• Introduction to Information Retrieval, Chapter 4
• Also of  interest, original papers
•  The Anatomy of a Large-Scale Hypertextual Web Search Engine, (pdf from Stanford publications collection) Brin, Sergey and Page, Lawrence, Proceedings of the Seventh International WWW Conference (WWW 7), 1998.
• Web Search for a Planet: The Google Cluster Architecture, Luiz Barroso, Jeffrey Dean, and Urs Hölzle,  In IEEE Micro, Vol. 23, No. 2, pages 22-28, March, 2003.
  
• MapReduce: Simplified Data Processing on Large Clusters, Jeffrey Dean and Sanjay Ghemawat, OSDI'04: Sixth Symposium on Operating System Design and Implementation, 2004, pp. 137-150.

• Remarks on index construction and query evaluation (pdf).
• Reading
• Introduction to Information Retrieval, Chapter 5
• Also of  interest
• Chris Anderson,  The Long Tail , Wired, October 2004 (link is to updated version - Dec. 14, 2004).
  

• Presentation: midterm summary and exam contents (pdf)
•  Summary of blackboard presentation of compression and some numbers (pdf):
  
• Reading
•  Introduction to Information Retrieval, Chapter 7  (mostly brings together ideas we have encountered at various points during our discussion of query evaluation - see remarks in midterm summary.)
  
• Review Introduction to Information Retrieval, Section 2.3  (did not have time to cover in class).
• Also of interest
• Description of several bit-level variable-length encodings of positive integers, including Elias gamma-code and delta-code covered in class:  *Modern Information Retrieval Section 7.4.5.
• A. Moffat and J. Zobel, Self- indexing inverted files for fast text retrieval, ACM Transactions on Information Systems, Vol. 14, No. 4 (Oct. 1996), pgs 349-379.

• Presentation on search refinement (pdf)
• Reading
• Introduction to Information Retrieval, Chapter 9
• Also of interest
• Optimizing Search Engines using Clickthrough Data, Thorsten Joachims, Proc. Conf. on Knowledge Discovery in Data (SIGKDD), 2002, pp. 133–142.
  
• Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions,   Gediminas Adomavicius,  Alexander Tuzhilin; IEEE Transactions on Knowledge and Data Engineering, vol. 17,  no. 6,  pp. 734-749,  June 2005.

• Presentation on collaborative filtering (pdf) with corrections
  
• Presentation on clustering, Part I (pdf)
• Reading
• Introduction to Information Retrieval, Chapter 16,  Introduction and Sections 16.1, 16.2, and 16.4.
• Introduction to Information Retrieval, Chapter 17,  Introduction and Sections 17.1, 17.2,  and 17.6.
• Take-home exam distributed at end of class.

• Presentations on clustering (pdf):  k-means details;  hierarchical clustering: agglomerative
• Today we looked at clustering meta-search engines Clusty and iBoogie
  
• Reading
• Introduction to Information Retrieval, Chapter 17,  Sections 17.3, 17.4,  and 17.8.
• Also of interest:
• Introduction to Information Retrieval, Chapter 16, Section 6.3 is recommended if you are going to read research papers on clustering.  We will touch on external evaluation criteria very briefly.
• Introduction to Information Retrieval, Chapter 17,  Sections 17.5 and 17.7 are recommended but not required.

• Class presentation (pdf) on divisive clustering and external measures of cluster quality
• Reading
• Introduction to Information Retrieval, Chapter 10
• Also of interest:
• A tutorial on spectral clustering, Ulrike von Luxburgh, Statistics and Computing , Vol 17, no. 4, pp. 395-416 (Springer, Dec. 2007).  (pdf here)
  

• Class presentation (pdf) on XML for information retrieval;  figure (pdf) giving tree model for books
• See April 9 for final presentation notes on near-duplicate document detection.
  
• The XML mark-up of Hamlet was done by Jon Bosak and can be found at http://www.cafeconleche.org/examples/shakespeare.  The version we looked at in class was obtained by using an XQuery query in the XQuery Sandbox example tool on the eXist Project Web site.  The eXist Project is centered around eXist-db, which is (in their words)  "an open source database management system entirely built on XML technology."
• Assignment 4 due today

• Reading
• Introduction to Information Retrieval, Chapter 19, Section 19.6

• Class presentation (pdf) on near-duplicate document detection (final) for April 7 and today.
  
• Reading
• Introduction to Information Retrieval, Chapter 20,  Sections 20.1-20.3.

• Take-home exam distributed at end of class.
• Reading
  
• nothing new
• Also of interest
• Multimedia IR:  Indexing and Searching, Christos Faloutos,  Chapter 12 in *Modern Information Retrieval.  Includes a discussion of characterizing images using color histograms.
• Image Similarity Search with Compact Data Structures,  Qin Lv, Moses Charikar, and Kai Li. 13th Conf. on Information and Knowledge Management (CIKM), ACM, Nov. 2004.  (Reports part of Princeton CASS project.)
• Web site: Princeton CASS: Content-Aware Search Systems - Demo of image "search by example"
  
• Web site:  Retrievr  search images by sketch (or example). 
  

• HOT OFF THE PRESS Research on enhancing Google Image search using image content:  PageRank for Product Image Search, Yushi Jing and Shumeet Baluja, Intern. World Wide Web Conf.(WWW), 2008. (pdf here)
  

• Take-home exam due at beginning of class.
• Reading
  
• nothing new

• closing summary (only discussed last two slides in class)
  

* on reserve in the Engineering Library