Scoring documents in a linked database

• US 7,269,587 B1
• Filed: 12/01/2004
• Issued: 09/11/2007
• Est. Priority Date: 01/10/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Page, Lawrence
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US11/000,375
• Time in Patent Office: 1,014 Days
• Field of Search: 707/7, 707/10, 715/501.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24573 using data annotations, e.g. user-defined metadata
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 16/382 using citations hypermedia G06F16/94
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method assigns importance ranks to nodes in a linked database, such as any database of documents containing citations, the world wide web or any other hypermedia database. The rank assigned to a document is calculated from the ranks of documents citing it. In addition, the rank of a document is calculated from a constant representing the probability that a browser through the database will randomly jump to the document.

Claims

1. A computer implemented method for calculating an importance rank for N linked nodes of a linked database, the method comprising:

(a) selecting an initial N-dimensional vector p₀, wherein each component of p₀ represents a probability that a user will start at a given node, wherein each node of the N linked nodes is a computer-readable document containing information;

(b) computing an approximation p_n to a steady-state probability p_∞

, wherein each component of p_∞

represents a probability that the user will randomly end up at a particular node after following a number of forward links, in accordance with the equation p_n=Aⁿp₀, where A is an N×

N transition probability matrix having elements A[i][j] representing a probability of moving from node i to node j; and

(c) determining a rank r[k] for a node k from a k^th component of p_n, wherein r[k] represents an importance of the information contained in node k.

2. The method of claim 1 wherein the matrix A is chosen so that an importance rank of a node is calculated, in part, from a weighted sum of importance ranks of backlink nodes of the node.

3. The method of claim 2 wherein the importance rank of each of the backlink nodes is weighted in dependence upon the total number of links in the backlink node.

4. The method of claim 1 wherein the matrix A is chosen so that an importance rank of a node is calculated, in part, from a constant α

representing the probability that a surfer will randomly jump to the node.

5. The method of claim 1 wherein the matrix A is chosen so that an importance rank of a node is calculated, in part, from a measure of distances between the node and backlink nodes of the node.

6. The method of claim 1 wherein the initial N-dimensional vector p₀ is selected to represent a uniform probability distribution.

7. The method of claim 1 wherein the initial N-dimensional vector p₀ is selected to represent a non-uniform probability distribution, wherein a predetermined set of nodes is given a large initial probability relative to other nodes.

8. A computer implemented method for calculating an importance rank for each of N linked web page documents, the method comprising:

(a) selecting an initial N-dimensional vector p₀, wherein each component of p₀ represents an initial estimate of a probability that a user will start at a given web page document;

(b) computing an approximation p₀ to a steady-state probability p_∞

, wherein each component of p_∞

represents an estimate of a probability that the user will randomly end up at a particular web page document, in accordance with the equation p_n=Aⁿp₀, where A is an N×

N transition probability matrix having elements A[i][j] representing a probability of moving from web page document i to web page document j; and

(c) determining a rank r[k] for a web page document k from a k^th component of p_n, wherein r[k] represents an importance of the information contained in a particular web page document k.

9. The method of claim 8 wherein the matrix A is chosen so that an importance rank of a given web page document is calculated, in part, from a weighted sum of importance ranks of web page documents backlinked to the given web page document.

10. The method of claim 9 wherein the importance rank of each of the backlinked web page documents is weighted in dependence upon the total number of links in the backlinked web page document.

11. The method of claim 8 wherein the matrix A is chosen so that an importance rank of a web page document is calculated, in part, from a constant α

representing the probability that a surfer will randomly jump to the web page document.

12. The method of claim 8 wherein the matrix A is chosen so that an importance rank of a web page document is calculated, in part, from a measure of distances between the web page document and backlink nodes of the web page document.

13. The method of claim 8 wherein the initial N-dimensional vector p₀ is selected to represent a uniform probability distribution.

14. The method of claim 8 wherein the initial N-dimensional vector p₀ is selected to represent a non-uniform probability distribution, wherein a predetermined set of web page documents is given a large initial probability relative to other web page documents.