US6871202B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for ranking web page search results
Assignee: Starboard Value Intermediate Fund Lp As Collateral Agent
•
Filing: 2003-05-06
•
Granted: 2005-03-22
•
Expires: 2023-05-06
Abstract
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.
Inventors
- 👤 Andrei Z. Broder
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 16:33
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/953; G06F16/9538; G06F16/951; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99937; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
70 words
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.
Claim 2
Independent Claim
70 words
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.
Claim 3
Dependent Claim
30 words
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.
Claim 4
Dependent Claim
25 words
The method as recited in claim 2 , wherein the attractor matrix is created by determining pages in the adjacency matrix which are externally endorsed.
Claim 5
Dependent Claim
17 words
The method as recited in claim 3 , wherein the attractor matrix is created using human endorsement.
Claim 6
Dependent Claim
36 words
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.
Claim 7
Dependent Claim
15 words
The method as recited in claim 1 , wherein the eigenvector is the primary eigenvector.
Claim 8
Dependent Claim
57 words
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.
Claim 9
Dependent Claim
30 words
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.
Claim 10
Dependent Claim
21 words
The method as recited in claim 1 , wherein the pages are results from a search of the World Wide Web.
Claim 11
Independent Claim
144 words
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.
Claim 12
Independent Claim
144 words
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.
Claim 13
Dependent Claim
16 words
The system as recited in claim 10 , wherein the database is the World Wide Web.
Claim 14
Independent Claim
69 words
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.
Claim 15
Independent Claim
69 words
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.
Claim 16
Dependent Claim
23 words
The method as recited in claim 12 , wherein the additional information regarding respective pages indicates whether the respective pages are externally endorsed.
Claim 17
Dependent Claim
26 words
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.
Claim 18
Dependent Claim
21 words
The method as recited in claim 12 , wherein the pages are results from a search of the World Wide Web.
Claim 19
Dependent Claim
18 words
The method as recited in claim 1 , further comprising multiplying the additional matrix with a probability matrix.
Claim 20
Dependent Claim
36 words
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.
References Cited (Backward Citations)
US5873056A
Cited
US5832470A
Cited
US6285999B1
Cited
US5895470A
Cited
US5835905A
Cited
US6026399A
Cited
US5930788A
Cited
US6389436B1
Cited
US6073135A
Cited
US6112203A
Cited
US6138113A
Cited
US6321220B1
Cited
US6549896B1
Cited
US6560600B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2008-03-21 | 2008-09-20 | 2009-03-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2012-03-21 | 2012-09-20 | 2013-03-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2016-03-21 | 2016-09-20 | 2017-03-22 | $7700.00 | Window Closed / Lapsed |