Method and apparatus for ranking web page search results

• US 6,871,202 B2
• Filed: 05/06/2003
• Issued: 03/22/2005
• Est. Priority Date: 10/25/2000
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Broder, Andrei Z.
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US10/431,644
• Publication Number:
  US 20040111412A1
• Time in Patent Office: 686 Days
• Field of Search: 707/3, 707/4, 707/5, 707/7, 707/101, 707/10, 707/6, 715/501.1
• 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 for ranking pages, the method comprising:

building a neighborhood graph of a plurality of pages;

generating an adjacency matrix based on the neighborhood graph;

determining at least one additional matrix to be combined with the adjacency matrix;

forming a linear combination of the adjacency matrix and the additional matrix to produce a resultant matrix;

determining an eigenvector of the resultant matrix; and

ranking the pages using the eigenvector.

2. The method as recited in claim 1, wherein the additional matrix is at least one of an attractor matrix, a non-attractor matrix, a cocitation matrix, and a bibliographic matrix.

3. The method as recited in claim 2, wherein the attractor matrix is created by determining pages in the adjacency matrix which are externally endorsed.

4. The method as recited in claim 3, wherein the attractor matrix is created using human endorsement.

5. The method as recited in claim 3, wherein the additional matrix is the non-attractor matrix, and the method further comprises dividing the non-attractor matrix so that pages stored on a same server are grouped together.

6. The method as recited in claim 1, wherein the eigenvector is the primary eigenvector.

7. The method as recited in claim 1, further comprising:

determining a power low distribution of the eigenvector;

assigning a number of bits used to store the ranking of each page in a plurality of categories;

analyzing the power low distribution to determine a granularity of the categories; and

assigning each page to one of the categories.

8. The method as recited in claim 1, further comprising:

generating a hub score for a particular page using eigenvector coefficients of a plurality of pages neighboring the particular page.

9. The method as recited in claim 1, wherein the pages are results from a search of the World Wide Web.

16. The method as recited in claim 1, further comprising multiplying the additional matrix with a probability matrix.

17. The method as recited in claim 16, wherein the additional matrix is the attractor matrix, and the method further comprises dividing the attractor matrix so that pages stored on a same server are grouped together.

10. A system for searching a database and producing ranked results, the system comprising:

a database;

a server including an index of pages in the database; and

,

a user connected to the server, the user and the server forming at least part of a network;

wherein the user sends a query to the server;

the server runs the query against the index to produce search results including a plurality of pages;

the server builds a neighborhood graph of the plurality of pages;

the server generates an adjacency matrix based on the neighborhood graph;

the server determines at least one additional matrix to be combined with the adjacency matrix;

the server forms a linear combination of the adjacency matrix and the additional matrix to product a resultant matrix;

the server determines an eigenvector of the resultant matrix; and

the server ranks the pages using the eigenvector.

11. The system as recited in claim 10, wherein the database is the World Wide Web.

12. A method for ranking pages, the method comprising:

determining a neighborhood of a plurality of pages;

determining respective relationship values between every two pages in the neighborhood based on respective links thereby producing determined respective relationship values;

modifying the determined respective relationship values based on additional information regarding respective pages thereby producing modified determined respective relationship values; and

ranking the pages based on the modified determined respective relationship values.

13. The method as recited in claim 12, wherein the additional information regarding respective pages indicates whether the respective pages are externally endorsed.

14. The method as recited in claim 12, wherein the additional information regarding respective pages indicates whether the respective pages are externally deemed to be avoided.

15. The method as recited in claim 12, wherein the pages are results from a search of the World Wide Web.