US7216123B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods for ranking nodes in large directed graphs
Assignee: Leland Stanford Junior University
•
Filing: 2003-08-22
•
Granted: 2007-05-08
•
Expires: 2023-08-22
Abstract
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.
Inventors
- 👤 Sepandar D. Kamvar
- 👤 Taher H. Haveliwala
- 👤 Glen Jeh
- 👤 Gene Golub
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 10:54
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/951; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99937
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
180 words
A computer implemented method for computing ranks in a linked database, the method comprising: obtaining a local rank vector associated with a selected subset of nodes in the linked database, wherein each component of the local rank vector represents a local rank of a node in the selected subset of nodes; obtaining a block rank vector associated with the linked database, wherein each component of the block rank vector represents a block rank of a subset of nodes in the linked database, wherein the subset is one of a plurality of subsets of nodes defined by a partition of the nodes in the linked database; selecting a component of the block rank vector corresponding to the selected subset of nodes; selecting a component of the local rank vector corresponding to a selected node in the selected subset of nodes; combining the selected component of the block rank vector and the selected component of the local rank vector to obtain a global rank for the selected node; and storing the global rank of the selected node on a computer readable medium.
Claim 2
Dependent Claim
180 words
A computer implemented method for computing ranks in a linked database, the method comprising: obtaining a local rank vector associated with a selected subset of nodes in the linked database, wherein each component of the local rank vector represents a local rank of a node in the selected subset of nodes; obtaining a block rank vector associated with the linked database, wherein each component of the block rank vector represents a block rank of a subset of nodes in the linked database, wherein the subset is one of a plurality of subsets of nodes defined by a partition of the nodes in the linked database; selecting a component of the block rank vector corresponding to the selected subset of nodes; selecting a component of the local rank vector corresponding to a selected node in the selected subset of nodes; combining the selected component of the block rank vector and the selected component of the local rank vector to obtain a global rank for the selected node; and storing the global rank of the selected node on a computer readable medium.
Claim 3
Dependent Claim
26 words
The method of claim 1 wherein obtaining the local rank vector comprises receiving the local rank vector from a computer that calculated the local rank vector.
Claim 4
Dependent Claim
20 words
The method of claim 1 wherein obtaining the local rank vector comprises selecting components of a preexisting global rank vector.
Claim 5
Dependent Claim
37 words
The method of claim 1 wherein obtaining the local rank vector comprises forming a local link matrix comprising link weights between nodes of the selected subset and computing the local rank vector from the local link matrix.
Claim 6
Dependent Claim
35 words
The method of claim 1 further comprising classifying the nodes of the linked database into subject classes and creating the partition of the nodes into the plurality of subsets in accordance with the subject classes.
Claim 7
Dependent Claim
20 words
The method of claim 1 further comprising obtaining a plurality of local rank vectors associated with the plurality of subsets.
Claim 8
Dependent Claim
32 words
The method of claim 1 wherein obtaining the block rank vector comprises forming a reduced link matrix for the linked database and computing the block rank vector from the reduced link matrix.
Claim 9
Dependent Claim
44 words
The method of claim 7 wherein forming the reduced link matrix comprises using a set of preference weights associated with the subsets to alter elements of the reduced link matrix so that the block rank vector is customized in accordance with the preference weights.
Claim 10
Dependent Claim
21 words
The method of claim 1 further comprising calculating a final rank from the global rank using an iterative link-based ranking technique.
Claim 11
Dependent Claim
24 words
The method of claim 1 further comprising using the global rank to determine an order of presentation of the selected node among other nodes.
Claim 12
Dependent Claim
118 words
A computer implemented method for computing a rank value for a node in a linked database, the method comprising: partitioning nodes of the linked database into K subsets according to a classification of the nodes, wherein K comprises the number of subsets produced by the partitioning; computing K local rank vectors for the K subsets of the nodes; computing a block rank vector from a K×K reduced link matrix; computing a global rank vector from the local rank vectors and the block rank vector; selecting a component of the global rank vector corresponding to the node to obtain the rank value for the node; and storing the rank value of the selected node on a computer readable medium.
Claim 13
Dependent Claim
118 words
A computer implemented method for computing a rank value for a node in a linked database, the method comprising: partitioning nodes of the linked database into K subsets according to a classification of the nodes, wherein K comprises the number of subsets produced by the partitioning; computing K local rank vectors for the K subsets of the nodes; computing a block rank vector from a K×K reduced link matrix; computing a global rank vector from the local rank vectors and the block rank vector; selecting a component of the global rank vector corresponding to the node to obtain the rank value for the node; and storing the rank value of the selected node on a computer readable medium.
Claim 14
Dependent Claim
58 words
The method of claim 11 wherein computing the K local rank vectors comprises arranging a link matrix for the linked database into a block-diagonal form corresponding to the partition of the nodes into subsets; forming K local link matrices from blocks of the link matrix, and computing the K local rank vectors from the K local link matrices.
Claim 15
Dependent Claim
23 words
The method of claim 11 wherein computing the K local rank vectors comprises executing a link-based ranking algorithm on a local link matrix.
Claim 16
Dependent Claim
20 words
The method of claim 13 wherein the link-based ranking algorithm comprises calculating a principal eigenvector of the local link matrix.
Claim 17
Dependent Claim
21 words
The method of claim 13 wherein the link-based ranking algorithm comprises performing a singular value decomposition of the local link matrix.
Claim 18
Dependent Claim
24 words
The method of claim 13 wherein the link-based ranking algorithm comprises forming a vector representing the row sums or column sums of the matrix.
Claim 19
Dependent Claim
22 words
The method of claim 11 wherein computing the K local rank vectors comprises dividing a preexisting global rank vector into K parts.
Claim 20
Dependent Claim
38 words
The method of claim 11 wherein computing the block rank vector comprises forming a reduced link matrix whose elements represent links between the subsets of the partition, and calculating the block rank vector from the reduced link matrix.
Claim 21
Dependent Claim
43 words
The method of claim 18 wherein forming the reduced link matrix comprises computing a block link weight between a first block and a second block by adding together weights of links from nodes in the first block to nodes in the second block.
Claim 22
Dependent Claim
22 words
The method of claim 18 further comprising customizing the reduced link matrix using a set of preference weights associated with the subsets.
Claim 23
Dependent Claim
55 words
The method of claim 11 wherein computing the global rank vector from the local rank vector and a block rank vector comprises: computing an estimated global rank vector from the local rank vector and a block rank vector; computing the global rank vector from the estimated global rank vector using an iterative link-based ranking technique.
Claim 24
Dependent Claim
31 words
The method of claim 11 wherein computing the K local rank vectors is performed at K distributed computers, and wherein computing the global rank vector is performed at a central computer.
Claim 25
Dependent Claim
30 words
The method of claim 11 wherein the linked database is a distributed collection of hypertext documents and the classification of the nodes is based on URL addresses of the nodes.
Claim 26
Dependent Claim
22 words
The method of claim 11 wherein the classification of the nodes is a predetermined subject classification of documents in the linked database.
Claim 27
Dependent Claim
22 words
The method of claim 11 wherein the classification of the nodes is computationally determined from a link structure of the linked database.
Claim 28
Dependent Claim
22 words
The method of claim 11 wherein the classification of the nodes is computationally determined from a similarity of content associated with nodes.
Claim 29
Dependent Claim
100 words
A computer implemented method for computing a rank value for a block of nodes in a linked database, the method comprising: partitioning nodes of the linked database into subsets according to a classification of the nodes; forming a reduced link matrix whose elements represent links between the subsets of the partition; calculating a block rank vector from the reduced link matrix; selecting a component of the block rank vector corresponding to the block of nodes to obtain the rank value for the block of nodes; and storing the rank value for the block of nodes on a computer readable medium.
Claim 30
Dependent Claim
100 words
A computer implemented method for computing a rank value for a block of nodes in a linked database, the method comprising: partitioning nodes of the linked database into subsets according to a classification of the nodes; forming a reduced link matrix whose elements represent links between the subsets of the partition; calculating a block rank vector from the reduced link matrix; selecting a component of the block rank vector corresponding to the block of nodes to obtain the rank value for the block of nodes; and storing the rank value for the block of nodes on a computer readable medium.
Claim 31
Dependent Claim
43 words
The method of claim 27 wherein forming the reduced link matrix comprises computing a block link weight between a first block and a second block by adding together weights of links from nodes in the first block to nodes in the second block.
Claim 32
Dependent Claim
22 words
The method of claim 27 wherein the classification of the nodes is a predetermined subject classification of documents in the linked database.
Claim 33
Dependent Claim
22 words
The method of claim 27 wherein the classification of the nodes is computationally determined from a link structure of the linked database.
References Cited (Backward Citations)
US20030208478A1
Cited
US6285999B1
Cited
US6799176B1
Cited
US6112202A
Cited
US6665837B1
Cited
US6138113A
Cited
US6922685B2
Cited
US6584468B1
Cited
US6560600B1
Cited
US20040111412A1
Cited
US6871202B2
Cited
US20030208482A1
Cited
US20030204502A1
Cited
US20040024752A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2010-05-07 | 2010-11-06 | 2011-05-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2014-05-07 | 2014-11-06 | 2015-05-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2018-05-07 | 2018-11-06 | 2019-05-08 | $7700.00 | Window Closed / Lapsed |