• A proof that eigen decomposition in fact gives the basis for low-rank approximation of a matrix.(Only for mathematically brave).
• The first and probably the best paper about LSI (it is missing a couple of figures, and the notation is slightly clumsy to read, but it gives the best motvation for LSI analysis
• A nice explanation of LSI and its myriad applications--done in an web-friendly way
• A more comprehensive paper about LSI scheme. It also has a realistic example where LSI is able to retrieve documents that pure vector space analysis wouldn't.(Read only up to and including Sec 3.2)

• J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. To appear in Journal of the ACM. Also appears as IBM Research Report RJ 10076, May 1997. (Defintive paper on A/H computation)
  • L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report, Stanford University, 1999. (Good paper on Page Rank computation)
• A paper that shows that page rank-like ideas have been used in science as far back as 1940 (with the 1940 one being in economics)
• A mathematical analysis of Pagerank (and how to subvert it..)
• These are three conference papers that I discussed in the class:
  • Paper by Ng. et. al. in IJCAI 2001 that analyzes stability of A/H and Page-rank compuation.
  • Paper by Haveliwala in WWW 2002 that describes how to compute topic-sensistive versions of page rank.
  • Paper by Haveliwala on efficient computation of page rank.
  • A paper that adds a boost to the page rank of recent pages..
    • A paper that studies the effect of recency on the pagerank
  • Trust Rank paper
  • Aardvark paper
• Beyond Page Rank: Machine Learning for Static Ranking

(Distributed) Indexing

• Class discussion based in part on this chapter from Manning et. al.
  • Indexing the World-wide Web: The Journey So Far

Crawling

• The Mercator Paper The HTML version of the paper. The project page.
  • A more recent public-domain crawler (WWW-2008 best paper): IRLbot: Scaling to 6 Billion Pages and Beyond
• Focused crawling paper by soumen chakrabarti et. al.
• Focused crawling using context graphs by Diligentil et. al. This is the one which uses search engines to figure out the pages pointing to the seed pages.

Cluster computing

• Google linux cluster (read first three pages to get an idea on how Google processes a query on a parallel linux cluster with tons of replication)

Social Networks

Tutorial article on small world and scale-free networks
• Small World Phenomena
• Scale-free networks
  • a longer paper
• Navigation in a small world (decentralized search) (1 page)
  • Longer version with proofs
• Comparision of trust propagation methods over Epinions trust matrix
• Trust Rank paper
• Aardvark paper

Overall Seach Engine

• Anatomy of a large sale hyper-textual web search engine. Brin and Page. The Google paper.
  • Amit Singhal's google blog post on what Google currently does... (July 2008)
  • On some feline tips for improving Google ranking of a page.
  • Google linux cluster (read first three pages to get an idea on how Google processes a query on a parallel linux cluster with tons of replication)
  • Challenges in Websearch Engines (Henzinger, Motwani, Silverstein))
  • Clever Project at IBM Almaden has a lot of interesting papers on link structure analysis, focused crawling and community clustering.
  • Mining the Link Structure of the world-wide web Chakrabarti, Dorm et. al. IEEE Computer. Nov 1999.

Clustering

Required readings: 16 and 17 17 from the IR book draft.
• A comparison of clustering methods for Text data (by Vipin Kumar et. al.)
• Global clustering using locality sensitive hashing (Haveliwala et al)
• local clustering using Suffix Trees in Grouper

Text Classification & Collaborative and Content-based Filtering

• Chapter on Text Classification from Manning et al's book
  • An excerpt on Naive-Bayes Classifier from Mitchell's textbook (scanned; 19mb)
  • Here is an early paper on using NBC to do spam detection..
    • Paper on a system called "Libra" that uses an extended version of NBC (vector of bags model of text) to do Book Recommendation. Read the section titled "Learning a profile"
    • Here is a neat paper that tries to analyze why NBC seems to work more often than it should..
    • Here is a paper that compares co-training and EM appraoches based on NBC classifers on text classification tasks.
    • Here is a paper on adversarial classification (and its application to SPAM filtering)
• An overview and empirical evaluation of collaborative filtering approaches
  • Another paper that contains a brief description of the collaborative filtering idea (page 2, section titled "Pure collaborative filtering"). In addition, it also describes how to combine content-based and collaborative filtering (from National Conf. on AI, 2002)
  • Adapting LSI techniques for collaborative filtering; and their success in Netflix prize

Database refresher readings

• A brief SQL Tutorial. Also, here is an on-line hands-on tutorial
• (Optional) Query Optimization Tutorial by Suraji Choudhury. Paper. Here are the Slides

XML as a Semi-structured Language

• XML tutorial (see at least the XML Basic part)
• an Xquery Tutorial
  • An Xquery Interpreter
  • W3C's Xquery Page (definitive--don't even try to print it unless you own half of Tonto National Forest).

Semantic Web

• Semantic Web paper from Scientific American by Tim Berners-Lee, Jim Hendler and Ora Lassila.
  • A course on semantic web--with good lectures
  • Semantic Web activity resource page on W3C
  • Folksonomies...

Information Extraction

• Overview paper on information extraction

• Wrapper Learning: Accurately and reliably extracting data from the web: A machine learning approach

• Web-scale information extraction in Know-it-all (Here is a page with other recent papers from this project)
  • SemTag and Seeker: Bootstrapping the semantic web via automated semantic annotation (WWW 2003 Best Paper)

Data Integration

• Planning for Information Gathering: A tutorial survey. Lambrecht & Kambhampati

Query Optimization/Procesing in Data Integration

• Joint Use of Multiple Learned Statistics for Improving Online Source Selection (this version is closer to what we discussed in class on [Apr 27, 2004]).
  • Learning source statistics for plan optimization in data integration (BibFinder paper)

Collection Selection (Text data aggregation)

• Paper on collection selection (with a bit of emphasis on handling overlap). Read sections 1, 2 and 3 at least.

Combining Database and Information Retrieval

All of the following are short papers...

• Paper on Soft-Joins
• Paper on keyword search on databases (BANKS) (There is a longer paper in ICDE 2002
• Paper on Imprecise queries (There is a longer paper in ICDE 2006)
• Paper on optimization issues in DB/IR
• VLDB 2004 Tutorial in IR/DB by Ricardo Baeza-Yates

Web Services

• A Snapshot of Public Web Services

Background Refreshers

1. Some basics of linear algebra (vectors, matrices, eigen values).
   • Nice lecture-format description of SVD (see lectures 4 and 5)
   • An informal description of principal components analysis.
     • This one gives a mathematical intuition
     • This one by Jordan does a nice introduction (from a neural nets perspective).
2. Matrices, vectors spaces and Information Retrieval Berry et. al. (a math view of linear algebra in IR
3. Here are refreshers on database background.
   • Relational database background
   • SQL background