Gene Golub

US Patent:

7216123, May 8, 2007

Filed:

Aug 22, 2003

Appl. No.:

10/646331

Inventors:

Sepandar D. Kamvar - Palo Alto CA, US
Taher H. Haveliwala - Mountain View CA, US
Glen Jeh - San Francisco CA, US
Gene Golub - Stanford CA, US

Assignee:

Board of Trustees of the LeLand Stanford Junior University - Palo Alto CA

International Classification:

G06F 17/30

US Classification:

707 5, 707 7, 707 10, 7155011, 715513

Abstract:

Techniques for assigning ranks to nodes in a large linked database, such as world wide web or any other hypermedia database, partition the nodes so that the link matrix has a predominantly block-diagonal form. Within each block, a local rank is computed for nodes in the block, possibly by different computer in a distributed computing environment. A block rank is then estimated for each block as a whole, and may optionally include block-level weights to implement customized ranking. The local ranks and block ranks are then combined to form a global rank, which may be used to rank the nodes. Alternatively, a global rank vector for the database may be used as an initial vector in an iterative link-based ranking scheme to obtain more accurate global ranks for the nodes. The global rank vector may be divided to provide local rank vectors for use in subsequent applications of the method.

US Patent:

7028029, Apr 11, 2006

Filed:

Aug 23, 2004

Appl. No.:

10/925189

Inventors:

Sepandar D. Kamvar - Palo Alto CA, US
Taher H. Haveliwala - Mountain View CA, US
Gene H. Golub - Stanford CA, US

Assignee:

Google Inc. - Mountain View CA

International Classification:

G06F 17/30

US Classification:

707 5, 3 7, 7155011

Abstract:

A system and method is disclosed in which a ranking function for a set of document rank values is iteratively solved with respect to a set of linked documents until a first stability condition is satisfied. After such condition is satisfied, some of the ranks will have converged. The ranking function is modified to take into account these converged ranks so as to reduce the ranking function's computation cost. The modified ranking function is then solved until a second stability condition is satisfied. After such condition is satisfied more of the ranks will have converged. The ranking function is again modified and process continues until complete.