Princeton University Computer Science Dept.

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

Spring 2006

Part 1: topics in information retrieval and manipulation

• Class presentation now on line as pdf.
• Reading:
  • *Modern Information Retrieval, Chapter 1, Sections 1-3;
    
  • *Modern Information Retrieval Chapter 3.
  
  

• Class presentation on "Relevance by TREC method"  now on line as pdf.   
• Reading:
  • Voorhees, Ellen, Evaluation by highly relevant documents, Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2001, pp. 74 - 82.
• Also of interest:
  
• Hawking, David and Nick Craswell, Very Large Scale Retrieval and Web Search (pdf file - Preprint version),  in TREC: Experiment and Evaluation in Information Retrieval. Ellen M. Voorhees and Donna K. Harman editors,  MIT Press, 2005.
• Text REtrieval Conference (TREC) home page.

• Reading:
• *Modern Information Retrieval Chapter 1, section 1.4;  Chapter 2 sections 2.1-2.4 and 2.5.1 - 2.5.3.

• Reading:
• *Information Retrieval : Algorithms and Heuristics  Chapter 2, section 2.6 (preferrable) or *Modern Information Retrieval Chapter 2, section 2.7.2 
  
• Also of interest:
• Telcordia has a Web site for Latent Semantic Indexing, which contains, among other material, pointers to many other papers for those interested in learning more.

• Reading:
• *Information Retrieval : Algorithms and Heuristics  Chapter 2, section 2.4 (preferrable) or *Modern Information Retrieval Chapter 2, section 2.8

• Reading:
• *Mining the Web: Discovering Knowledge from Hypertext Data Chapter 7,  Sections 7.1-7.5
• Also of interest:
• (HITS algorithm) Kleinberg, Jon, Authoritative sources in a hyperlinked environment, Journal of the ACM, Vol. 46, No. 5(Sept. 1999), pp.604-632.
• (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. 

• Reading:
• *Modern Information Retrieval: Chapter 5,  Section 2 introduction and sub-sections 5.2.1 and 5.2.4.
• class notes on a sample of experimental comparisons

• Reading:
• What's New on the Web? The Evolution of the Web from a Search Engine Perspective,  A. Ntoulas, J. Cho,  and C. Olston,  WWW Conf. 2004.
• *Modern Information Retrieval Chapter 4, Chapter 8 sections 8.1, 8.2
  

• Of interest 
•  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.  (Small portion of the paper relates to index building.)
  
  

• Reading:
• Thomas Funkhouser, Patrick Min, Michael Kazhdan, Joyce Chen, Alex Halderman, David Dobkin, and David Jacobs, A Search Engine for 3D Models (local copy), ACM Transactions on Graphics, 22(1), January 2003.

• Reading:
• *Modern Information Retrieval Section 7.4.5
• class notes on indexing first used by Google (also see reading "of interest" for March 7)
• 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.

Part 2: topics in information discovery

• class notes on overview of clustering
  
• *Information Retrieval : Algorithms and Heuristics  Chapter 3, Section3.2
• * Chapter 16 "Clustering" in Information Retrieval: Data Structures and Algorithms, Frakes, William and Baeza-Yates, Ricardo, editors, Prentice Hall, 1992. Now on reserve at the Engineering Library. (more detailed than the first reading).

• Reading:
• summary of board presentation today
• notes on k-means by Martin Makowiecki
• *Mining the Web: Discovering Knowledge from Hypertext Data Chapter 4, Sections 4.1-4.5.  (There is some overlap with the reading for March 28.)
  

• Reading:
• class slides on cluster comparison and clustering applications we discussed prior to spring break
  

• Reading: 
• Graph Clustering and Minimum Cut Trees, G.W. Flake, K. Tsioutsiouliklis, R.E. Tarjan,  Internet Mathematics Vol. 1, No. 4: 385-408, 2004. Note that the algorithm presented in this paper is a variation of the one presented in class.  I cannot find a reference for the version I presented in class other than Kostas Tsioutsioulikis' dissertation (citation below).
  
• Also of interest:
• This discussion is based on results  presented in the Ph.D. dissertation of Konstantinos Tsioutsioulikis, Department of Computer Science, Princeton University, June 2002.

• Reading:
• Mining association rules between sets of items in large databases  Rakesh Agrawal, Tomasz Imieliński, Arun Swami, ACM SIGMOD 1993 (received 2003 SIGMOD "Test of Time Award" - judged to be best paper from 1993 SIGMOD 10 years later)

• Reading:
•  Slide of  large itemset algorithm used today
  
• Mining Surprising Periodic Patterns Jiong Yang, Wei Wang, Philip S. Yu  Data Mining and Knowledge Discovery(DMKD), Volume 9, Number 2 September 2004  pp. 189 - 216.
• 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.
• Also of interest:
• Beyond Market Baskets: Generalizing Association Rules to Dependence Rules,  Craig Silverstein, Sergey Brin, Rajeev Motwani, Data Mining and Knowledge Discovery (DMKD), Volume 2, Number 1, Springer Science+Business Media B.V (formerly Kluwer Academic Publishers B.V.) January 1998 pp. 39 - 68.
• Cyclic association rules Ozden, B.; Ramaswamy, S.; Silberschatz, A.    International Conference on  Data Engineering, IEEE, 1998, pp. 412-421.

• Reading:
• pdf of slides  from Chris Richbourg's presentation on RACOFI 
  
• pdf of slides (1up version =  pg per slide) from John Son's presentation on the use of trust in recommendation systems (6up version)
• RACOFI: A Rule-Applying Collaborative Filtering System, Anderson et. al., Proc. IEEE/WIC COLA’03, Halifax, Canada, October 2003.
• Trust-aware Collaborative Filtering for Recommender Systems, Paolo Massa and Paolo Avesani, Proc.Intern. Conf. on Cooperative Information Systems,  Oct 2004.  Published by Springer as Lecture Notes in Computer Science Volume 3290, 2004.
• Trust in Recommender Systems, John O’Donovan & Barry Smyth, IUI’05, ACM, January 9–12, 2005.
• Trust-based Collaborative Filtering, Jianshu Weng, Chunyan Miao, Angela Goh and Dongtao Li, CIKM’05, ACM, Oct. 31–Nov. 5, 2005.
• A Trust-­enhanced Recommender System application: :Moleskiing, Avesani, Massa, and Tiella. 

Part 3: systems issues in delivering digital information

• Reading:
• class notes on web crawling
• class notes on focused web crawling
  
• *Mining the Web: Discovering Knowledge from Hypertext Data, Chapter 2.
• Intelligent Crawling On the World Wide Web with Arbitrary Predicates,"  Aggarwal, Al-Garawi, and Yu, Tenth International World Wide Web Conference (WWW10), 2001.
• Also of interest:
  
• *Mining the Web: Discovering Knowledge from Hypertext Data, Chapter 8, section 8.3.1
• Evaluating topic-driven web crawlers,   Filippo Menczer, Gautam Pant, Padmini Srinivasan, Miguel E. Ruiz,   Proc. Intern.ACM SIGIR Conf. on Research and Development in Information Retrieval  (SIGIR Conf.), ACM,  2001,  pages: 241 - 249.
  

• Reading:
• pdf of slides  from Joseph Bradley's presentation on latent Dirichlet allocation.
  
• Latent Dirichlet allocation, D. Blei, A. Ng, and M. Jordan, Journal of Machine Learning Research, 3:993–1022, January 2003.
• A survey of Web caching schemes for the Internet, Jia Wang. ,  ACM Computer Communication Review, 29(5):36-46, October 1999.
• A Web Caching Primer, Davison, B.D. IEEE Internet Computing, IEEE Vol. 5, Issue 4  Jul/Aug 2001  pgs 38-45.

• Also of interest:
• Web site Brian D. Davison's Web Caching and Content Delivery Resources: www.web-caching.com
  

• Reading:
• pdf of slides  from Frank Macreery's presentation on prediction of access.
• Selective Markov models for predicting Web page accesses,  Mukund Deshpande, George Karypis, ACM Transactions on Internet Technology (TOIT)  Vol. 4 ,  Issue 2  (May 2004) pgs: 163 - 184.
• Using path profiles to predict HTTP requests, S. Schechter, M. Krishnan and M.D. Smith, Proceedings of the Seventh International World-Wide Web Conference, 1998.  Published in Computer Networks and ISDN Systems, Volume 30, issues 1-7(1998), Elsevier Science B.V..

• Reading
• Content Delivery Networks: Status and Trends, Athena Vakali and George Pallis, IEEE Internet Computing. Nov.-Dec. 2003, pgs 68-74.
• Insight and Perspectives for Content Delivery Networks, George Pallis and Athena Vakali, Communications of the ACM, Vol. 49(1), 2006, pgs. 101-106.
• The many faces of publish/subscribe, Patrick Th. Eugster, Pascal A. Felber, Rachid Guerraoui, Anne-Marie Kermarrec  ACM Computing Surveys, Vol. 35 (2), June 2003m oo, 114-131.
  
• Also of interest:
• RFC 2616: Hypertext Transfer Protocol -- HTTP/1.1,  in particular Chapter 13: Caching. Obtain using ftp link from W3C Hypertext Transfer Protocal Overview page, under "Specifications, Drafts, Papers and Reports - HTTP Working Group,"
  
• Characterization of a Large Web Site Population with Implications for Content Delivery   L. Bent,  M. Rabinovich,  G. M. Voelker, Z. Xiao,  WWW 2004.
• Akamai Web site
• Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web (pdf from Akamai), David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, Daniel Lewin.  Proc. 29th ACM Symposium on Theory of Computing (STOC),  May 1997.
• Reliability and Security in the CoDeeN Content Distribution Network (local copy)  Limin Wang, KyoungSoo Park, Ruoming Pang, Vivek S. Pai, Larry Peterson, Proc. USENIX 2004 Annual Technical Conference, June 2004.

• Reading
• pdf of slides  from Sergio Garza's presentation on Cat-aCone
• pdf of slides from Michael Wenzel's presentation on music classification
• pdf of slides for final remarks
  
• Musical Genre Classification of Audio Signals (from Tanaetakis' site at U. Victoria), George Tzanetakis and Perry Cook, IEEE Trans. on Speech and Audio Processing, Vol. 10 (5), July 2002, pp. 293-302.
• Cat-a-Cone: an interactive interface for specifying searches and viewing retrieval results using a large category hierarchy, Marti Hearst and Chandu Karadi, Proc. 20th Intern. Conf. on Research and Development in Information Retrieval (SIGIR), ACM,  1997, pp. 246 - 255. HTML version in color with extra figures on authors' site.
  
• Also of interest:
• Browsing and querying in online documentation: A study of user interfaces and the interaction process,  Morten Hertzum and Erik Frokjaer, ACM Transactions on Computer-Human Interaction, 3(2), June 1996, pp. 136-161.
  

* on reserve in the Engineering Library