Scientific Computing Seminar

Date:

Friday, November 19, 2004

Time:

1:00pm-2:00pm

Location:

50A-5132

Seminar Speaker:

Sou-Cheng Choi, Stanford University
with Michael Saunders, Stanford University
John Tomlin, IBM Almaden Research Center

Title:

HOT-PageRank: Tuning in to the Traffic Channel

Abstract:

Google's celebrated PageRank model uses the stationary vector of a Markov chain to rank a large collection of web pages. This off-line sorting is used later by Google's search engine to rank pages that match a query.
Tomlin has proposed a maximum-entropy traffic-flow model to provide two alternative off-line orderings: TrafficRank and HOTS. We propose a further model, HOT-PageRank, that uses the HOTS solution to replace the uniform transition probabilities assumed in the PageRank Markov matrix.
We discuss techniques for speeding up matrix-vector products involving the Markov matrix. We also highlight PDCO, a primal-dual interior method for convex optimization, used to solve the traffic-flow problem.
We compare the ranking schemes on examples from the Harvard intranet and CiteSeer's computer science citations. Finally, we consider rank aggregation and find that a combined model usually provides more satisfactory results than any single scheme.

Sponsor of Seminar:

Xiaoye Li

Scientific Computing

Contact Esmond G. Ng EGNg@lbl.gov