Adaptive computation of ranking

• US 7,028,029 B2
• Filed: 08/23/2004
• Issued: 04/11/2006
• Est. Priority Date: 03/28/2003
• Status: Expired due to Term

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kamvar, Sepandar D., Haveliwala, Taher H., Golub, Gene H.
• Primary Examiner(s): METJAHIC, SAFET
• Application Number:
  US10/925,189
• Publication Number:
  US 20050027685A1
• Time in Patent Office: 596 Days
• Field of Search: 707/3, 707/100, 707/5, 707/101, 707/10, 706/15, 715/500
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/953 Querying, e.g. by the use of web search engines
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

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.

Claims

1. A method for determining document rank values, comprising:

iteratively solving a ranking function for a set of document rank values with respect to a set of linked documents until a first stability condition is satisfied;

modifying the ranking function so as to reduce the ranking function'"'"'s computation cost;

solving the modified ranking function until a second stability condition is satisfied so as to produce a solution of the modified ranking function; and

assigning respective ranks to at least a subset of the documents in the set of linked documents in accordance with the solution of the modified ranking function.

2. The method of claim 1, wherein the modifying includes identifying a subset of the document rank values that have converged to within a tolerance.

3. The method of claim 2, wherein the modifying includes removing a portion of the ranking function corresponding to the identified subset of the document rank values.

4. The method of claim 3, wherein the modifying includes modifying a portion of the ranking function corresponding to the identified subset of the document rank values.

5. The method of claim 1, wherein the first stability condition is satisfied after completing a first number of iterations of the ranking function.

6. The method of claim 1, wherein the second stability condition is satisfied after completing a second number of iterations of solving the modified ranking function.

7. The method of claim 1, wherein the first stability condition is satisfied after completing a first number of iterations of solving the ranking function, and wherein the first and second numbers of iterations are different.

8. The method of claim 1, wherein the first stability condition is satisfied when a percentage of the linked documents have a current rank which has converged to within a tolerance.

9. The method of claim 1, further including:

providing a matrix A where A(j,i) represents a directed link value from a document to a document j; and

wherein the ranking function includes the matrix and the modifying includes removing from the matrix those rows corresponding to documents whose respective current document rank value has converged to within a tolerance.

10. The method of claim 1, further including:

providing a matrix A where A(j,i) represents a directed link value from a document i to a document j; and

wherein the ranking function includes the matrix and the modifying includes removing from the matrix those columns corresponding to documents whose current document rank value has converged to within a tolerance.

11. The method of claim 1, further including:

providing a matrix A where A(j,i) represents a directed link value from a document i to a document j; and

wherein the ranking function includes the matrix and the modifying includes removing from the matrix those columns and rows corresponding to documents whose respective current document rank value has converged to within a tolerance.

12. A computer program product, for use with a computer system, the computer program product comprising:

instructions for iteratively solving a ranking function for a set of document rank values with respect to a set of linked documents until a first stability condition is satisfied;

instructions for modifying the ranking function so as to reduce the ranking functions computation cost;

instructions for solving the modified ranking function until a second stability condition is satisfied so as to produce a solution of the modified ranking function; and

instructions for assigning respective ranks to at least a subset of the documents in the set of linked documents in accordance with the solution of the modified ranking function.

13. The computer program product of claim 12, wherein the instructions for modifying include identifying a subset of the document rank values that have converged to within a tolerance.

14. The computer program product of claim 13, wherein the instructions for modifying include instructions for removing a portion of the ranking function corresponding to the identified subset of the document rank values.

15. The computer program product of claim 13, wherein the instructions for modifying include instructions for modifying a portion of the ranking function corresponding to the identified subset of the document rank values.

16. The computer program product of claim 12, further including instructions for satisfying the first stability condition after completion of a first number of iterations of the ranking function.

17. The computer program product of claim 12, further including instructions for satisfying the second stability condition after completion of a second number of iterations of solving the modified ranking function.

18. The computer program product of claim 17, further including instructions for satisfying the first stability condition after completion of a first number of iterations of solving the ranking function, and wherein the first and second numbers of iterations are different.

19. The computer program product of claim 12, further including instructions for satisfying the first stability condition when a percentage of the linked documents have a current rank which has converged to within a tolerance.

20. The computer program product of claim 12, further including:

instructions for providing a matrix A where A(j,i) represents a directed link value from a document i to a document j; and

wherein the ranking function includes the matrix and the instructions for modifying includes instructions for removing from the matrix those rows corresponding to documents whose respective current document rank value has converged to within a tolerance.

21. The computer program product of claim 12, further including:

instructions for providing a matrix A where A(j,i) represents a directed link value from a document i to a document j; and

wherein the ranking function includes the matrix and the instructions for modifying includes instructions for removing from the matrix those columns corresponding to documents whose current document rank value has converged to within a tolerance.

22. The computer program product of claim 12, further including:

instructions for providing a matrix A where A(j,i) represents a directed link value from a document i to a document j; and

wherein the ranking function includes the matrix and the instructions for modifying includes instructions for removing from the matrix those columns and rows corresponding to documents whose respective current document rank value has converged to within a tolerance.

23. A system for determining document rank values, comprising:

a computation module that iteratively solves a ranking function for a set of document rank values with respect to a set of linked documents;

a modification module that modifies the ranking function so as to reduce the ranking function'"'"'s computation cost; and

a control module that is configured to use the computation module to solve the ranking function until a first stability condition is satisfied, use the modification module to modify the ranking function, and use the computation module to solve the modified ranking function until a second stability condition is satisfied so as to produce a solution of the modified ranking function and assign respective ranks to at least a subset of the documents in the set of linked documents in accordance with the solution of the modified ranking function.

24. The system of claim 23, further including an identification module that identifies a subset of the document rank values that have converged to within a tolerance.

25. The system of claim 24, wherein the modification module includes removal instructions that remove a portion of the ranking function corresponding to the identified subset of the document rank values generated from the identification module.

26. The system of claim 24, wherein the modification module includes a modifier instructions that modify a portion of the ranking function corresponding to the identified subset of the document rank values generated from the identification module.

27. The system of claim 23, further including first convergence instructions corresponding to the first stability condition, the first convergence instructions identifying when a first number of iterations of solving the ranking function are completed.

28. The system of claim 27, further including second convergence instructions corresponding to the second stability condition, the second convergence identifying when the second stability condition is satisfied.

29. The system of claim 28, wherein the second stability condition corresponds to a second number of iterations of solving the ranking function, and wherein the first and second numbers of iterations are different.

30. The system of claim 23, further including a convergence percentage and a convergence module that identifies the first stability condition when a percentage of the linked documents equal to the convergence percentage have a current rank which has converged to within a tolerance.

31. A system for determining document rank values, comprising:

means for iteratively solving a ranking function for a set of document rank values with respect to a set of linked documents until a first stability condition is satisfied;

means for modifying the ranking function so as to reduce the ranking function'"'"'s computation cost; and

means for solving the modified ranking function until a second stability condition is satisfied;

wherein operation of the system produces a solution of the modified ranking function and assigns respective ranks to at least a subset of the documents in the set of linked documents in accordance with the solution of the modified ranking function.