MA 591R

Special Topics: Web Search, Information Retrieval, and Data Mining

WHEN & WHERE

Spring 2007, 3:00-4:15pm M W, Room 325, Harrelson Hall

DESCRIPTION

The focus is on the mathematical technology involved in building various kinds of information retrieval systems and search engines. The material will include classical methods such as latent semantic indexing systems along with various document clustering schemes and will proceed through more recent techniques based on nonnegative matrix factorizations. A primary facet involves studying web search with particular emphasis on the Google technology. It is hoped that upon successful completion of the course students will have amassed enough knowledge to build their own search engines. Material beyond the text, Google's PageRank and Beyond: The Science of Search Engine Rankings, will be drawn from a variety of recent research papers. The class will be conducted "seminar style" with students giving presentations throughout the term.

GRADING

Grades are determined on the basis of projects and presentations.

PRESENTATIONS

Shaina Race will speak March 19 on the paper by Patrik O. Hoyer titled Non-negative Matrix Factorization with Sparseness Constraints.

• Shaina's PowerPoint Presentation

• The matrix generation tool that Shaina used in her project can be found at The TMG download site

Anjela Govan will speak March 21 on "Algorithms for Clustering Data" from a book of the same name by Anil K. Jain and Richard C. Dubes.

• Anjela's Presentation (pdf)

• Anjela's demo tools

Teresa Selee will speak March 26 on the paper by J. Higham and Milla Kibble titled A Unified View of Spectral Clustering

• Teresa's Presentation (pdf)

• Teresa's Handouts (pdf)

Hui Xie will speak March 28 on the paper by Litvak titled The Effect of New Links on Google Pagerank

• Hui Xie's Presentation (ppt)

• Hui's reference material on Markov chains (pdf)

Rebecca Wills will speak April 2 on the paper by Gyongyi, Garcia-Molina, and Pedersen titled Combating Web Spam with Trust Rank

• Rebecca Wills' Presentation (pdf)

• Rebecca Wills' Maple Example (mws)

Russell Albright and Jim Cox from SAS will speak on April 9 (during the SAS field trip described below). Russ will speak on predictive modeling concepts and algorithms, and Jim will address issues in text mining.

• Russell Albright's SAS presentation (ppt)

Barbara Ball from the College of Charleston will speak April 12 on "Recent Developments in Clustering"

• The emphasis is on Fiedler (or spectral) clustering techniques. Numerical experiments will also be discussed.

• Barbars's Presentation (pdf)

Mike Marshall from Fortune Interactive will speak April 16 on Search Engine Optimization.

• Links to Mike's materials for his presentation (Three MS Word docs) can be found on this page.

SAS Institute Field Trip

The class is scheduled to take a field trip to SAS institute on Monday, April 9, where they will be given a presentation and demo of SAS technology involving data and text mining. Below are directions and times.

• Meet in the lobby of building "S" on the SAS campus at 2:45 to sign in and receive security badges. To get to the SAS campus from Raleigh, take I-40 WEST toward the Raleigh-Durham Airport, and take Exit 287 at Harrison Avenue. At the top of the exit ramp, turn south onto Harrison avenue and then go left at the first traffic light onto SAS Campus Drive. Stop at the guard booth and tell the officer what your intent is.
• Here is a map of how to get to the SAS campus (pdf)

• Here is a map of the SAS campus (pdf)

• Russell Albright's SAS presentation (ppt)

TEXT BOOK

Google's PageRank and Beyond: The Science of Search Engine Rankings, by Amy Langville and Carl Meyer

• Available from Princeton University Press and Amazon.com

PREREQUSITES

Probability at the MA421 level and Linear Algebra at the MA523 or MA520 level

• Programming experience is required (MATLAB is acceptable)

SCHEDULE

FIRST CLASS:   January 10 (Wednesday)

HOLIDAY:   (MLK Day) January 15 (Monday)

SPRING BREAK:   March 5-9 (Mon-Fri)

LAST DAY TO DROP:   March 21 (Wednesday)

HOLIDAY:   (Easter Vacation) April 6 (Friday)

LAST CLASS:   All projects due on April 27 (Friday)

FINAL EXAM: There is no written final exam.

OUTLINE OF THE WEB SEARCH COMPONENT

Introduction to Web Search Engines

• A Short History of Information Retrieval
• An Overview of Traditional Information Retrieval
• Web Information Retrieval

Crawling, Indexing, and Query Processing

• Crawling
• The Content Index
• Query Processing

Ranking Webpages by Popularity

• The Scene in 1998
• Two Theses
• Query-Independence

The Mathematics of Google's PageRank

• The Original Summation Formula for PageRank
• Matrix Representation of the Summation Equations
• Problems with the Iterative Process
• A Little Markov Chain Theory
• Early Adjustments to the Basic Model
• Computation of the PageRank Vector
• Theorem and Proof for Spectrum of the Google Matrix

Parameters in the PageRank Model

• The α Factor
• The Hyperlink Matrix
• The Teleportation Matrix E

The Sensitivity of PageRank

• Sensitivity with respect to α
• Sensitivity with respect to H
• Sensitivity with respect to v^T
• Other Analyses of Sensitivity
• Sensitivity Theorems and Proofs

The PageRank Problem as a Linear System

• Properties of (I -- αS)
• Properties of (I -- αH)
• Proof of the PageRank Sparse Linear System

Issues in Large-Scale Implementation of PageRank

• Storage Issues
• Convergence Criterion
• Accuracy
• Dangling Nodes
• Back Button Modeling

Accelerating the Computation of PageRank

• An Adaptive Power Method
• Extrapolation
• Aggregation
• Other Numerical Methods

Updating the PageRank Vector

• The Two Updating Problems and their History
• Restarting the Power Method
• Approximate Updating Using Approximate Aggregation
• Exact Aggregation
• Exact vs. Approximate Aggregation
• Updating with Iterative Aggregation
• Determining the Partition
• Conclusions

The HITS Method for Ranking Webpages

• The HITS Algorithm
• HITS Implementation
• HITS Convergence
• HITS Example
• Strengths and Weaknesses of HITS
• HITS's Relationship to Bibliometrics
• Query-Independent HITS
• Accelerating HITS
• HITS Sensitivity

Other Link Methods for Ranking Webpages

• SALSA
• Hybrid Ranking Methods
• Rankings based on Traffic Flow

The Future of Web Information Retrieval

• Spam
• Personalization
• Clustering
• Intelligent Agents
• Trends and Time-Sensitive Search
• Privacy and Censorship
• Library Classification Schemes
• Data Fusion

REFERENCE BOOKS

Matrix Analysis and Applied Linear Algebra by C. D. Meyer

• Available from SIAM and Amazon.com

Understanding Search Engines: Mathematical Modeling and Text Retrieval by Michael Berry and Burray Browne, Second Ed.

• Available from SIAM and Amazon.com