Method and apparatus for ranking Web page search results

• US 6,560,600 B1
• Filed: 10/25/2000
• Issued: 05/06/2003
• Est. Priority Date: 10/25/2000
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: AltaVista Company (Apollo Global Management, Inc.)
• Inventors: Broder, Andrei Z.
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/696,922
• Time in Patent Office: 923 Days
• Field of Search: 707/2, 707/3, 707/5, 707/10, 707/513, 707/514, 707/100, 707/102, 707/4, 707/101, 707/103, 707/104, 707/501
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method and apparatus for ranking a plurality of pages identified during a search of a linked database includes forming a linear combination of two or more matrices, and using the coefficients of the eigenvector of the resulting matrix to rank the quality of the pages. The matrices includes information about the pages and are generally normalized, stochastic matrices. The linear combination can include attractor matrices that indicate desirable or “high quality” sites, and/or non-attractor matrices that indicate sites that are undesirable. Attractor matrices and non-attractor matrices can be used alone or in combination with each other in the linear combination. Additional bias toward high quality sites, or away from undesirable sites, can be further introduced with probability weighting matrices for attractor and non-attractor matrices. Other known matrices, such as a co-citation matrix or a bibliographic coupling matrix, can also be used in the present invention.

Claims

1. A method of ranking a plurality of pages identified during a search of a linked database, the method comprising:

forming a linear combination of two or more matrices, wherein each matrix includes information about at least a portion of the plurality of pages;

determining an eigenvector of the linear combination; and

ranking the plurality of pages based on the eigenvector.

2. The method, as set forth in claim 1, wherein the eigenvector is the principal eigenvector.

3. The method, as set forth in claim 1, wherein the matrices are stochastic matrices.

4. The method, as set forth in claim 1, wherein at least one of the matrices is an attractor matrix.

5. The method, as set forth in claim 4, wherein at least one of the matrices is a probability matrix for weighting the attractor matrix.

6. The method, as set froth in claim 1, wherein at least one of the matrices is a non-attractor matrix.

7. The method, as set froth in claim 6, wherein at least one of the matrices is a probability matrix for weighting the non-attractor matrix.

8. The method, as set forth in claim 1, wherein at least one of the matrices is a co-citation matrix.

9. The method, as set froth in claim 1, wherein at least one of the matrices is a bibliographic coupling matrix.

10. The method, as set froth in claim 1, wherein ranking the plurality of pages based on the eigenvector comprises:

determining ranking categories based on the number of pages to be ranked; and

classifying each page in one of the categories.

11. The method, as set forth in claim 10, further comprising:

allotting a fixed amount of storage for representing the rank of each page.

12. The method, as set forth in claim 10, wherein each bit in the fixed amount of storage represents one of the categories and the rank of each page is represented by the bit assigned to the page.

13. The method, as set forth in claim 1, further comprising:

combining eigenvector coefficients of neighboring pages to generate a hub score for at least one of the plurality of pages.

14. A computer program product for ranking a plurality of pages identified during a search of a linked database, the product comprising:

first program instructions for forming a linear combination of two or more matrices, wherein each matrix includes information about at least a portion of the plurality of pages;

second program instructions for determining an eigenvector of the linear combination; and

third program instructions for ranking the plurality of pages based on the eigenvector.

15. The product, as set froth in claim 14, wherein the eigenvector is the principal eigenvector.

16. The product, as set forth in claim 14, wherein the matrices are stochastic matrices.

17. The product, as set forth in claim 14, wherein at least one of the matrices is an attractor matrix.

18. The product, as set froth in claim 17, wherein at least one of the matrices is a probability matrix for weighting the attractor matrix.

19. The product, as set forth in claim 14, wherein at least one of the matrices is a non-attractor matrix.

20. The product, as set forth in claim 19, wherein at least one of the matrices is a probability matrix for weighting the non-attractor matrix.

21. The product, as set forth in claim 14, wherein at least one of the matrices is a co-citation matrix.

22. The product, as set forth in claim 14, wherein at least one of the matrices is a bibliographic coupling matrix.

23. The product, as set forth in claim 14, wherein the third program instructions are further operable to determine ranking categories based on the number of pages to be ranked;

and classify each page in one of the categories.

24. The product, as set forth in claim 23, wherein the third program instructions are further operable to allot a fixed amount of storage for representing the rank of each page.

25. The product, as set froth in claim 24, wherein each bit in the fixed amount of storage represents one of the categories and the rank of each page is represented by the bit assigned to the page.

26. The product, as set forth in claim 14, further comprising:

fourth program instructions for combining eigenvector coefficients of neighboring pages to generate a hub score for at least one of the plurality of pages.

27. A device for ranking a plurality of pages identified during a search of a linked database, the device comprising:

means for forming a linear combination of two or more matrices, wherein each matrix includes information about at least a portion of the plurality of pages;

means for determining an eigenvector of the linear combination; and

means for ranking the plurality of pages based on the eigenvector.

28. The device, as set forth in claim 27, wherein the eigenvector is the principal eigenvector.

29. The device, as set forth in claim 27, wherein the matrices are stochastic matrices.

30. The device, as set forth in claim 27, wherein at least one of the matrices is an attractor matrix.

31. The device, as set forth in claim 30, wherein at least one of the matrices is a probability matrix for weighting the attractor matrix.

32. The device, as set forth in claim 27, wherein at least one of the matrices is a non-attractor matrix.

33. The device, as set forth in claim 32, wherein at least one of the matrices is a probability matrix for weighting the non-attractor matrix.

34. The device, as set forth in claim 27, wherein at least one of the matrices is a co-citation matrix.

35. The device, as set forth in claim 27, wherein at least one of the matrices is a bibliographic coupling matrix.

36. The device, as set forth in claim 27, wherein the means for ranking the plurality of pages based on the eigenvector comprises:

means for determining ranking categories based on the number of pages to be ranked; and

means for classifying each page in one of the categories.

37. The device, as set forth in claim 36, further comprising;

means for allotting a fixed amount of storage for representing the rank of each page.

38. The device, as set forth in claim 36, wherein each bit in the fixed amount of storage represents one of the categories and the rank of each page is represented by the bit assigned to the page.

39. The device, as set forth in claim 27, further comprising;

means for combining eigenvector coefficients of neighboring pages to generate a hub score for at least one of the plurality of pages.