Tom Mangan Boolean term matching

Tom Mangan

• Tom Mangan

Boolean term matching

• Boolean term matching

Boolean term matching

• Boolean term matching

• Sergey Brin and Larry Page

• Reputation based ranking

• PageRank

Count links to a page

• Count links to a page

• Weight links by how many come from a page

• Further weight links by the reputation of the linker

Convergence requires:

• Convergence requires:

Markov chain

• Markov chain

• The conditional probability of each future state depends only on the present state

• Markov matrix

• Transition matrix of a Markov chain

Row-stochastic

• Row-stochastic

• Stationary vector gives long-term probability of each state

• All eigenvalues λ ≤ 1

Amy Langville and Carl Meyer

• Amy Langville and Carl Meyer

• Exploit dangling nodes

• Solve a system instead of iterating

Re-order rows and columns so that dangling nodes are lumped at bottom

• Re-order rows and columns so that dangling nodes are lumped at bottom

• Solve

• Compute

• Normalize

In testing, Algorithm 1 reduces the time necessary to find the PageRank vector by a factor of 1-6

• In testing, Algorithm 1 reduces the time necessary to find the PageRank vector by a factor of 1-6

• This time is data-dependent

First improvement came from finding zero rows in

• First improvement came from finding zero rows in

• Now find zero rows in

Reorder rows and columns so that all submatrices have zero rows at bottom

• Reorder rows and columns so that all submatrices have zero rows at bottom

• Solve

• For i = 2 to b, compute

• Normalize

Finding submatrices of zero rows takes longer than time saved in solve step

• Finding submatrices of zero rows takes longer than time saved in solve step

• L & M wait until all submatrices are reordered to solve primary

As each submatrix is isolated, send it out for parallel solving

• As each submatrix is isolated, send it out for parallel solving