Princeton University Computer Science Dept.

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

Spring 2017

• Class presentation slides (pdf): introduction,  classic IR
  
• Reading:
  
  • 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.
• Optional 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). 

• Assignment 0:  register on Piazza if you aren't already and add yourself to cos 435.
• Assignment 1, Part 1  - due 2/15
• Class presentation slides (pdf):   continuation of slides posted for Feb 6
  
• Reading:
•  Introduction to Information Retrieval, 
• Chapter 6: Sections 6.2, 6.3, and 6.4 except 6.4.4.
  
• Optional Reading:
  
• Introduction to Information Retrieval, Chapters 11 and 12 on probabilistic models

WEEK 2
Mon. Feb. 13:  Extending the models. Using links.

• Class presentation slides: link analysis for ranking
  
• 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. )

• Assignment 1, Part 2 - due Wed. 2/22
• Class presentation slides (pdf): no new slides
  
• Reading: reading for evaluation originally here now under Feb 22.

• Assignment 2  due Wed. 3/1
• 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): index structure, use and construction
• Reading:
  
• Introduction to Information Retrieval:
• Chapter 2: Section 2.4.
  
• Chapter 3: Introduction and Section 1.
• Chapter 7: Section 7.1, except 7.1.6, and Section 7.2

• Assignment 3 , due Wed. 3/8.
• Class presentation slides (pdf): continuation of slides used Monday (2/27)
• Reading:
• Introduction to Information Retrieval,
  
• Chapter 2: 2.1.2,  2.2.2 and 2.2.4.
• Chapter 4, Sections 1 thru 3.
• Optional Reading:
  
• Introduction to Information Retrieval: sections 2.1.1, 2.2.1, 2.2.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.

WEEK 5
Mon. Mar. 6: class canceled

Wed.  Mar. 8:  Index compression

• Class notes: Compression, Part 1(pdf)
  
• Reading:
• Introduction to Information Retrieval Chapter 5:  Sections 1 and  2.

• Short project proposal due today, March 13  11:55 pm by DropBox submission.  See Project page for details.
  
• Take-home exam out Wednesday March 17
  
• class notes: Compression, Part 2 (pdf)
  
• Reading:
• Introduction to Information Retrieval:
• Chapter 5: Section 3
• Chapter 2: Section 2.3
  
• 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 notes: Zipf's and Heap's Laws can be found in Part 2 of the compression summary;  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, Elsevier (Morgan_Kaufmann Division), 2003.  Chapter 2 and Chapter 8, section 8.3.1

• Take-home midterm exam March 15, 2017 to Friday March 17, 2017
• The exam will look much like a problem set.  You can work on it at any time during the two days.  It is not meant to take two days.
  

Spring break

• Class presentation slides (pdf): near-duplicate documents
• Reading:
• Introduction to Information Retrieval, Chapter 19, Section 19.6
• Also of interest:
• Henzinger, M., Finding Near-Duplicate Web Pages: A Large-Scale Evaluation of Algorithms, Conf. on Research and Development in Information Retrieval (SIGIR), 2006.
• Manku, G. S., Jain, A.,  Das Sarma, A., Detecting Near-Duplicates for Web Crawling, Intern. World Wide Web Conf. (WWW), 2007.

• Assignment 4  - due Wed. 4/5
• Class presentation slides (pdf): latent semantic indexing;  clustering, Part 1
• Reading:
  
• Mining of Massive Data Sets (Rajaraman, Leskovec and Ullman), Chapter 11, Section 3.  See General Information for access to digital copies.
• 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

• 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
• Recommended reading:
• Introduction to Information Retrieval, Chapter 17,  Sections 17.5 and 17.7 . 

• Assignment 5  - due Wed. 4/12
• Class presentation slides (pdf): social network analysis
• Reading
  
• Mining of Massive Data Sets. (Rajaraman, Anand; Leskovec, Jure; Ullman,  Jeffrey D, Cambridge University Press. 2011), Chapter 10, Section 1
  

• Recommended reading:
• Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook, Lars Backstrom and Jon Kleinberg, Proc. Conf. on Computer Supported Cooperative Work and Social Computing (CSCW), ACM, 2014, pp. 831-841.
• Also of interest:
• An Experimental Study of the Small World Problem, Jeffrey Travers and Stanley Milgram, Sociometry, Vol. 32, No. 4, American Sociological Assoc. (Dec., 1969), pp. 425-443.
• Planetary-scale views on a large instant-messaging network, Jure Leskovec and Eric Horvitz, Proc. Intern. Conf. on World Wide Web (WWW),  ACM, 2008, pp, 915-924.

• Class presentation slides:  continuation of slides posted for April 5.
• Reading
  
• Mining of Massive Data Sets. (Rajaraman, Anand; Leskovec, Jure; Ullman,  Jeffrey D, Cambridge University Press. 2011), Chapter 10, Sections 2 and 4.

• Assignment 6 (last assignment)  - due Wed. 4/19
  
• Class presentation slides:  search refinement, personalization, content-based recommendations
  
• 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.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.
• 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): collaborative-based recommender systems and final remarks on personalization
  
• Reading: 
• Mining of Massive Data Sets, Chapter 9, Sections 3 thru 6 except 9.3.3.

• Also of interest: 
• An Analytical Comparison of Approaches to Personalizing PageRank, Sep Kamvar,  Taher Haveliwala and Glen Jeh, Stanford University Technical Report. June, 2003.
  
• 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 (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
• TinEye - reverse image search (find where exact image occurs)

• Class presentation slides (pdf): deep web 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 (pdf), 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): 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 - March 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.
• The paper on Earlybird:  Earlybird: Real-Time Search at Twitter, Busch et. al., IEEE 28th International Conference on Data Engineering, 2012, pp. 1360-1369.  You may skip section VI on concurrency management.
• 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): see slides for May1 for distributed computing; closing remarks
  
• No required reading
• Reading of interest
• Trains of Thought: Generating Information Maps, Dafna Shaha, Carlos Guestrin, and Eric Horvitz, Intern. World Wide Web Conf. (WWW), ACM, 2012, pp. 899-908.
• 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.
  
• Netflix Spilled Your Brokeback Mountain Secret, Lawsuit Claims, Ryan Singel, Wired, Dec. 17, 2009.
• A Face Is Exposed for AOL Searcher No. 4417749, Michael Barbaro and Tom Zeller Jr., The New York Times, August 9, 2006
  
• '10 Concerts' Facbook Meme May Reveil More Than Musical Tastes, Christopher Mele and Daniel Victor, The New York Times, April 28, 2017
• The Internet of mess things,  opinion by Steven J. Vaughan-Nichols, Computerworld, May 3, 2017
• Google says the internet of things' smarts will save energy, Cade Metz, Wired, April 29, 2015.
  
• Internet Usage Statistics, Internet World Stats