Princeton University Computer Science Dept.

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

Spring 2014

• Class presentation slides (pdf): introduction
  
• Reading:
  
  • Bush, Vannevar,  "As We May Think,"  Atlantic Monthly,  July 1945:  The Atlantic html version or  ACM page containing link to pdf version (with original illustrations). 
  • Introduction to Information Retrieval :
    
  • Preface: introduction (pgs xxxi and top xxxii)
  • Chapter 1: introduction and Section 1.1.
  • Chapter 19: introduction and Section 19.1.

• Class presentation slides (pdf):  classic IR
• Reading:
•  Introduction to Information Retrieval, 
• Chapter 6: Sections 6.2, 6.3, and 6.4 except 6.4.4. (originally for Feb. 5)
• Optional Reading:
  
• Introduction to Information Retrieval, Chapters 11 and 12 on probabilistic models
• Assignment 0:  register on Piazza if you aren't already and add yourself to cos 435.
  

• Class presentation slides: extended model; link-based ranking
• Problem Set 1 (pdf) is now available, due Feb. 19
  
• Reading
• Introduction to Information Retrieval :
  
• Chapter 1: Sections 1.2 and 1.4
• Chapter 21, all except 21.2.3
  
• Chapter 15: Section 15.4 (read only for basic ideas)
• 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 slides (pdf):  evaluation
  
• Reading:
• Introduction to Information Retrieval:
• Chapter 8, all except 8.7
• Chapter 19: Section 19.4
  
• Optional Reading:
• Introduction to Information Retrieval, Section 8.7
• Also of interest:
• Text REtrieval Conference (TREC) Proceedings
• Clarke, Charles L. A. ,Craswell, Nick and Voorhees, Ellen M., Overview of the TREC 2012 Web Track (pdf), Proc. Twenty-First Text REtrieval Conference (TREC 2012), National Institute of Standards and Technology (NIST), 2012.
  
  
  

• Class presentation slides (pdf): indexing
• Problem Set 1 (pdf) due today!
• Reading:
  
• Introduction to Information Retrieval:
• Chapter 2: Sections 2.3, and 2.4.
  
• Chapter 3: Introduction and Section 1.
• Chapter 7: Section 7.1, except 7.1.6, and Section 7.2

• no new notes or reading
  

• Class presentation slides (pdf): index construction;  blow-up of B⁺ tree example
• Problem Set 2 due today!
• Reading:
• Introduction to Information Retrieval,
  
• Chapter 2: Section 2.1.2,  2.2.2 and 2.2.4.
• Chapter 4, Sections 1 thru 3.
• details on B+ trees in Database Management Systems by Raghu Ramakrishnan and Johannes Gehrke (Third Edition, McGraw-Hill, 2003): Chapter 10, Sections 3-6 (pp. 344-356).  Book on reserve in Engineering Library.
  
• Optional Reading:
  
• Introduction to Information Retrieval: sections 2.1.1, 2.2.1, 2.2.3

• Notes on compression lecture - Part 1 (pdf)
  
• Reading:
• Introduction to Information Retrieval, Chapter 5:  Sections 1 and  2.

• Notes on compression lecture - Part 2 (pdf)
  
• Problem Set 3 (pdf) due today!
• Reading:
• Introduction to Information Retrieval, Chapter 5: Section 3
• skip pointers covered in Section 2.3 assigned earlier
• Also of interest
• 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.
• 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.

• Class presentation slides (pdf): distributed computing
• Reading:
  
• Rajaraman, Anand; Leskovec, Jure; Ullman,  Jeffrey D,  Mining of Massive Data Sets, Cambridge University Press. 2011.  (You can download a pdf file of the latest version of the book - Jan. 2014 as of this writing):
• Chapter 2:  Introduction through 2.3.2
  
• Introduction to Information Retrieval, Chapter 20: Section 3
• Optional reading:
• The paper on Percolator:   Large-scale Incremental Processing Using Distributed Transactions and Notifications(pdf), Daniel Peng and Frank Dabek, in 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI '10), 2010.
• Also of interest
• 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.
• "Bigtable: A Distributed Storage System for Structured Data" , Fay Chang, et. al., In 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI '06), 2006.
  
• MapReduce: simplified data processing on large clusters, Jeffrey Dean and Sanjay Ghemawat, Communications of the ACM,  51(1), Jan. 2008.  (Special 50^th Anniversary issue: Breakthrough research: a preview of things to come.)
• The Apache Hadoop project

• Class presentation slides (pdf):  Web crawling
• Reading:
• Introduction to Information Retrieval, Chapter 20,  Sections 1 and 2.
• Also of interest:
• *Chakrabarti, Soumen, Mining the Web: Discovering Knowledge from Hypertext Data, Chapter 2 and Chapter 8, section 8.3.1

• Class presentation slides (pdf): search refinement and personalization
• Reading:
• Introduction to Information Retrieval, Chapter 9, Section 1  except 9.1.2, 9.1.4, 9.1.5
• Mining of Massive Data Sets, Chapter 9, Sections 1 and 2, except 9.2.2, 9.2.3, 9.2.7
  
• Also of interest:
• Personalizing Web Search using Long Term Browsing History, Matthijs and Radlinski, International Conf. on Web Search and Data Mining (WSDM), ACM, 2011.
• A Large-scale Evaluation and Analysis of Personalized Search Strategies (pdf), Song and Wen, Sixteenth Intern.World Wide Web Conference, (WWW2007), 2007.
• Time is of the Essence: Improving Recency Ranking Using Twitter Data,  Anlei Dong et. al., Proc. Intern. Conf. on World Wide Web  (WWW), ACM,  2010, pp. 331-340.
• The Adaptive Web,  P.  Brusilovsky,  A. Kobsa, W. Nejdl, eds.,  Lecture Notes in Computer Science book series Vol 4321, Springer, 2007. This  book contains several relevant chapters.  Chapter 6: Personalized Search on the World Wide Web by A. Micarelli, F.Gasparetti, F.Sciarrone and S. Gauch is of particular interest.  The chapters are available as pdf files to members of the Princeton University community by accessing them from the princeton.edu domain.
• Google: Bing Is Cheating, Copying Our Search Results by Danny Sullivan, Feb 1, 2011 at 8:45am ET and
  Bing Admits Using Customer Search Data, Says Google Pulled ‘Spy-Novelesque Stunt’ by Matt McGee, Feb 1, 2011 at 1:56pm ET,  both on Search Engine Land.

• Class presentation slides (pdf): recommender systems and search
  
• Reading: 
  
• Mining of Massive Data Sets, Chapter 9, Sections 3 thru 6 except 9.3.3.
  
• An Analytical Comparison of Approaches to Personalizing PageRank (pdf), Sep Kamvar,  Taher Haveliwala and Glen Jeh, Stanford University Technical Report. June, 2003.
• Also of interest: 
• Matrix Factorization Techniques for Recommender Systems, Koren, Bell and Volinsky, IEEE Computer, 42(8), August 2009, pp. 42-49.
• Modeling Relationships at Multiple Scales to Improve Accuracy of Large Recommender Systems,  Bell, Koren and Volinsky, International Conf. on Knowledge Discovery and Data Mining  (KDD), ACM 2007. 
  
• Scalable Collaborative Filtering with Jointly Derived Neighborhood  Interpolation Weights, Bell and Koren, IEEE International Conference on Data Mining, 2007.
• Netflix Awards $1 Million Prize and Starts a New Contest by Steve Lohr, New York Times' Bits Blog,  Sept. 21 2009.   (The new contest was canceled due to privacy concerns.)

• Class presentation slides:  matrix factorization; latent semantic indexing
  
• Reading:
• Introduction to Information Retrieval, Chapter 18.  IMPORTANT:  Example 18.4 in Chapter 18 is incorrect.  Please see a correction.

• Problem Set 4 due today!
• Class presentation slides (pdf): clustering Part 1
  
• Reading:
• Introduction to Information Retrieval, Chapter 16,  Introduction and Sections 16.1, 16.2, and 16.4 except 16.4.1.

• Optional reading:
• 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 16: Section 6.4.1.

Project progress meetings with Professor LaPaugh NEXT week  -watch

• Class presentation slides (pdf): clustering Part 2
• Reading
• Introduction to Information Retrieval, Chapter 17,  Introduction, Sections 17.1 thru 17.4,  17.6 and 17.8
• Optional reading:
• Introduction to Information Retrieval, Chapter 17,  Sections 17.5 and 17.7 are recommended but not required.

• Problem Set 5 (pdf) due today!
• Class presentation slides (pdf): near-duplicate documents
  
• Reading:
• Introduction to Information Retrieval, Chapter 19, Section 19.6

• Class presentation slides (pdf): non-text retrieval
  
• No required reading
  
• Also of interest - today's material drawn from these references:
• Query by image and video content: the QBIC system, Flickner, M., et.al.,  IEEE Computer,  IEEE Computer Society, 28(9) p23-32, Sept 1995.
• 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.)
• Integrating wavelets with clustering and indexing for effective content-based image retrieval, E Yildizer, AM Balci, and TN Jarada, Knowledge-Based Systems, Vol. 13, July 2012 , Elsevier, pp 55-66.
  
• VisualRank: Applying PageRank to Large-Scale Image Search, Yushi Jing and Shumeet Baluja, IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(11), p 1877 - 1890,  IEEE, 2008.

• Also of interest - sites to visit in demo
• Princeton CASS: Content-Aware SearchSystems Demos click on VARY image
  
• Pixolution demo
• Google images -  click on camera in search box
  

• Problem Set 6 (pdf) due today!
• Class presentation slides (pdf): deep seb search
  
• No required reading
  
• Also of interest - today's material drawn from these references:
• Structured Data on the Web, Michael J. Cafarella, Alon Halevy,  and  Jayant Madhavan,  Communications of the ACM (CACM), Vol 54 (2) February 2011, pp 72-79.
• Harnessing the Deep Web: Present and Future (pdf), Jayant Madhavan,  Loredana Afanasiev,  Lyublena Antova, and Alon Halevy,  4th Biennial Conference on Innovative Data Systems Research (CIDR), Jan. 2009.
• Web-scale extraction of structured data, Michael J. Cafarella, Jayant Madhavan, and Alon Halevy, ACM SIGMOD Record,  Vol. 37 (4) December 2008.
• Searching the deep web, Alex Wright, Communications of the ACM, Vol. 51 No. 10 (Oct. 2008),  pages 14-15.
• Google's Deep-Web Crawl (pdf), Jayant Madhavan, David Ko, Lucja Kot, Vignesh Ganapathy, Alex Rasmussen, and Alon Y. Halevy,  34^th Intern. Conf. on Very Large Data Bases, VLDB Endowment, Aug. 2008.
• Crawling deep web entity pages, Yeye He, Dong Xin, Venkatesh Ganti, Siriram Rajaraman, and Nirav Shah, Proc. Intern. Conf. on Web Search and Data Mining (WSDM), ACM, 2013, pp. 355-364.
• Accessing the deep web,  Bin He, Mitesh Patel, Zhen Zhang, and Kevin Chen-Chuan Chang,  Communications of the ACM, Vol. 50 No. 5 (May 2007), pages 94-101.
• Searching for Hidden-Web Databases, Luciano Barbosa and Juliana Freire., Proceedings of the 8th ACM SIGMOD International Workshop on Web and Databases (WebDB), pp. 1-6, ACM 2005.  (A more recent, more complicated version of the crawler is described at the 2007 WWW conf.)
• Towards web-scale structured web data extraction, Tomas Grigalis,  Proc. Intern. Conf. on Web Search and Data Mining (WSDM), ACM, 2013, pp. 753-757.

• Class presentation slides (pdf):  XML
  
• The XML mark-up of Hamlet was done by Jon Bosak and can be found at http://www.cafeconleche.org/examples/shakespeare.
  
• Reading:
• Introduction to Information Retrieval, Chapter 10, Sections 1, 2, and 5.
• Optional Reading:
• Introduction to Information Retrieval, Chapter 10, Sections 3 and 4.
• Also of interest
• Cognetic Systems Inc. is a company that sells an XML database product called XQuantum, which uses XQuery.    They have an XQuery demo site that offers XML versions of Shakespeare plays (all 37) - choose "Full-Text Search" at left. 
• Taranov et. al., Sedna: Native XML Database Management System (Internals Overview), Proc. SIGMOD Intern. Conf. on Management of Data (SIGMOD'10), ACM, 2010, pgs 1037-1046.

• Class presentation slides (pdf):  social networks - final including section on structure
  
• No required reading
  
• Also of interest
  
• #TwitterSearch: A Comparison of Microblog Search and Web Search,  Jaime Teevan, Daniel Ramage and Meredith Ringel Morris, Proc. of the Intern. Conf. on Web Search and Data Mining (WSDM), ACM, 2011, pp. 35-44.
  
• What is Twitter, a Social Network or a News Media?, Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon, Proc. Intern. Conf. on World Wide Web  (WWW), ACM,  2010, pp. 591-600.
  
• We Feel Fine and Searching the Emotional Web, Sepandar D. Kamvar and Jonathan Harris, Proc. of the Intern. Conf. on Web Search and Data Mining (WSDM), ACM, 2011, pp. 117-126.
• We Feel Fine: An Almanac of Human Emotion by Sep Kamvar and Jonathan Harris, video on YouTube.  See also the book We Feel Fine: An Almanac of Human Emotion by Sep Kamvar & Jonathan Harris, Scribner, Dec. 2009.
• Learning from Bullying Traces in Social Media, Jun-Ming Xu, Kwang-Sung Jun, Xiaojin Zhu and Amy Bellmore,  Proc. Conf. of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL HLT), Assoc. for Computational Linguistics, 2012, pp. 656-666.
  

• Class presentation slides (pdf):  privacy
• No required reading
• Optional Reading in social network structure
  
• Networks, Crowds, and Markets:  Reasoning about a Highly Connected World, (Easley, and Kleinberg, Cambridge University Press, July 19, 2010)  Chapter 2, Sections 1-3; Chapter 3.
• Also of interest for privacy issues
  
• Netflix Spilled Your Brokeback Mountain Secret, Lawsuit Claims, Ryan Singel, Wired, De. 17, 2009.
• A Face Is Exposed for AOL Searcher No. 4417749, Michael Barbaro and Tom Zeller Jr., The New York Times, August 9, 2006
• Engineering Privacy, Sarah Spiekermann and Lorrie Vaigth Cranor, IEEE Transactions on Software Engineering 35(1), IEEE, pp .67-82, Jan./Feb 2009.
• You Might Also Like: Privacy Risks of Collaborative Filtering, Calandrino, J.A, Kilzer, A.,  Narayanan, A.,  Felten, E.W., and Shmatikov, V.,  IEEE Sym. on Security and Privacy (SP), 2011, pp. 231 - 246.
  
• Personalization and privacy: a survey of privacy risks and remedies in personalization-based systems,  Eran Toch, Yang Wang and Lorrie Faith Cranor, User Modeling and User-Adapted Interaction, Vol.22 (1-2), Springer, 2012, pp. 203-220.

• Class presentation slides (pdf):  closing
  
• No required reading

Project Demonstrations between May 14 and May 19

* on reserve in the Engineering Library