CSE 494/598 Information Retrieval, Mining and Integration on the Internet

Instructor: Subbarao Kambhampati (Office Hours: T/Th 2:45--3:45PM BY 560)

******Check out the notes from the latest offering (now *with* videos!)*****

Note for Undergrads:I am particularly interested in seeing more undergraduate students register for this course.

1. How do search engines work? Why are some pp better than others?
2. Can we think of the web as a big database/knoweldge base and support efficient database style query processing?
3. Can we find useful pearls and patterns in the mass of accessible data on the Internet?

This course will be breadth-oriented introduction to the issues involved in answering these questions.

Prerequisites: CSE 310 required. Other courses that will help include CSE 471 (AI) CSE 412 (Databases) and CSE 450 (Algorithms). I am hoping that students have had at least one of these 4-level courses already, but won't insist on them. Students planning to register for this course are encouraged to talk to the instructor (via email at rao wholivesat asu dot edu).

Grading: The grading will be based on class participation, exams and projects.

Textbooks: There is no prescribed textbook. We will read papers (see the reading list.)

Overview: The best overview is the list of topics and lecture notes from the previous offering (shown below).

Additional pointers:

• Check out what students say about the last offering of this course in CEAS student evaluations.
• Check out what earlier students did in the last offering of the course
• Check out what some of the earlier students are doing now.

Lecture Notes & Audio

Spring 2007; T/Th 3:15--4:30PM BYAC 190

Instructor: Subbarao Kambhampati (Office Hours: T/Th 4:30--5:30PM BY 560)

(TA: Bhaumik Chokshi. Office Hours: Wed: 10-11AM BY557BB)

CEAS student evaluations from Spring 2007..

1. Introduction [Jan 16, 2007]
   • Audio of the lecture of [Jan 16, 2007]

2. Text retrieval; vectorspace ranking
   • Audio of the lecture of [Jan 18, 2007] (Continuation of how IR/Mining/Integration/Social Networks change to support web; three big themes of the Web; start of traditional information retrieval--precision/recall curves)

   • Audio of the lecture of [Jan 23, 2007] (Long discussion on how relevance function should *really* be computed vs. how it is done in traditional information retrieval; Basics of IR architecture (stemming etc); Ranking approaches--boolean and Jaccard)

   • Audio of the lecture of [Jan 25, 2007] (Discussion on Marginal Relevance; Discussion on Vector similarity metrics; tf/idf weighting; expected problems with vector similarity metrics. Relevance Feedback

3. Correlation analysis & Latent Semantic Indexing
   • Audio of the lecture of [Jan 30, 2007] (Relevance feedback reprise; Correlation analysis; Motivating LSI/dimensionality reduction )

   • Audio of the lecture of [Feb 1, 2007] (The BIG LSI/SVD class. LSI basics. Its use in retrieval and clustering. Connections between LSI and feature selection and non-linear correlation analysis)

4. Indexing; Crawling; Exploiting tags in web pages
   • Audio of the lecture of [Feb 6, 2007] (Retrieval with inverted indexes; digression on anytime computations; Salient differences between web search vs. traditional IR (challenges vs. opportunities), Crawling )

   • Audio of the lecture of [Feb 8, 2007] (Distributed indexes; digression into collection selection; Crawling--management of URL frontier; Exploiting Tags; anchor text, google bombs, spoofing, need for link analysis, beginning of social network analysis)

5. Social Network Analysis
   • Audio of the lecture of [Feb 13, 2007] (Social networks--measures of importance and centraliy, small world phenomena as observed in kevin bacon game; erdoch number; *uniform* random graphs and explaining small world phenomena in terms of them; argument that real world networks are not uniform random but rather exhibit power law distribution of degree; discussion on properties of power law distribution; digression into Zipfs' law, Heap's law and Benford's law.)

   • Audio of the lecture of [Feb 15, 2007] (Bit more on power law distrivutions; Differences between scale-free and (uniform) random networks; navigation of small worlds; revisiting Zipf and Heap's laws. [From A/H slides below] Start of link analysis for assessing page importance. A/H computation. Their connection to the eigen vector computation.

6. Link Analysis in Web Search (A/H; Pagerank)
   • Audio of the lecture of [Feb 20, 2007] Reprise on page importance; Computing authorities and hubs from link structure; explanation as to why the computation converges; ways of making link matrix sensitive to query and to resistant to intra-domain link spamming; tyranny of majority in A/H computation; the corresponding stability issue (and a solution)

   • Audio of the lecture of [Feb 22, 2007] All about page rank. Viewing link structure of the web as defining a markov chain and viewing page importance in terms of stationary distribution of the markov chain. Variations on the random surfer model and the corresponding variations in page rank. Efficient computation of page rank.

   • Audio of the lecture of [Feb 28, 2007] Comparative analysis of pagerank vs. A/H analysis. Adversarial ideas for defeating pagerank (pagefarms etc). Variants of pagerank (Topic-specific page rank; trust-based pagerank; recency-sensitive page rank) and how all of them play with the Reset distribution. Discussion of Anatomy of Google paper

   • Audio of the lecture of [Mar 1, 2007]. Wide-ranging class discussion on search engines--several interesting topics and discussions done.

7. Clustering
   • Audio of the lecture of [March 6, 2007] Basics for clustering and its applications in search and IR. K-means clustering and its limitations.
   • Audio of the lecture of [March 8, 2007] Clustering 2 (Variations on K-means; Bisecting K-means; Hierarchical clustering; Hierarchical Agglomerative Clustering; Buckshot algorithm; Additional directions in clustering; Start of classification

8. Text Classification
   • Audio of the lecture of [March 20, 2007]KNN, Rochchio and Naive Bayes text classifiers. M-estimates and Laplacian Smoothing. Unigram models of Text Classification. (**Note: Only the first 10min or so got recorded due to a technical glitch**).

9. Filtering/Recommender Systems
   1. Optional slides on Map/Reduce
   2. Optional slides on Min-hash/LSH
   3. Optional slides on probabilistic latent semantic indexing
   • Audio of the lecture of [March 22, 2007]Feature selection approaches for text classification; Digression on dimensionality reduction vs. feature selection; SPAM filtering and observations on spam fighting (as well as ridiculing the class for not knowing the Python Spam sketch). Recommendation Systems--the issues. Content vs. Collaborative filtering
   • Audio of the lecture of [March 27, 2007]Content-based and Collaborative filtering techniques, and ways of combining them.

10. Why do we even care about databases in the context of web?
    • Audio of the discussion+lecture of [Apr 3, 2007]. First 45min are discussion arising from google news clustering paper. The last 30 min are introduction to databases and the web.

11. XML and handling semi-structured data + Semantic Web standards
    • Audio of the lecture of [Apr 5, 2007]. XML as a syntactic standard for representing structure
    • Audio of the lecture of [Apr 10, 2007]. Who makes XML?, XML & Meaning; XML Schema, XQUERY standard; XML and databases syntactic standard for representing structure
    • Audio of the lecture of [Apr 12, 2007]. Semantic Web & its Standards. RDF and RDF-Schema. Ending with who does the annotation.

12. Information Extraction
    • Audio of the lecture of [Apr 17, 2007]. 3 ways of annotating the web; collaborative tagging & Folksonomies; Information extraction begin; wrapper generation.
    • Audio of the lecture of [Apr 19, 2007]. Information extraction from unstructured text. Extracting facts and validating them. CBIOC project. Semtag/Seeker and annotating with respect to an ontology

13. Information/data Integration
    • Audio of the lecture of [Apr 24, 2007]. Discussion of Semtag/Seeker + Start of Information Integration. Variations of information integration.
    • Audio of the lecture of [Apr 26, 2007]. Data Integration Models.

14. Query Processing in Data Integration
15. End
    • Audio of the lecture of [May 1, 2007]. Discussion of (1) Soft-joins as a model for integrating databases with text fields (and string similarity metrics) (2) Query processing issues in data aggregation/integration. Learning and using source statistics (3) Ending spiel (with Big ideas)

16. Mini WWW-2007 Conference presentations [May 8, 2007]. (And here is the audio of the presentations).

Topics to come:
[May 1, 2007]: Query processing issues; DB/IR
[May  8, 2007]: Mini-Www-2007