US6725259B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Ranking search results by reranking the results based on local inter-connectivity
Assignee: Google LLC
•
Filing: 2003-01-27
•
Granted: 2004-04-20
•
Expires: 2023-01-27
Abstract
Abstract A search engine for searching a corpus improves the relevancy of the results by refining a standard relevancy score based on the interconnectivity of the initially returned set of documents. The search engine obtains an initial set of relevant documents by matching a user's search terms to an index of a corpus. A re-ranking component in the search engine then refines the initially returned document rankings so that documents that are frequently cited in the initial set of relevant documents are preferred over documents that are less frequently cited within the initial set.
Inventors
- 👤 Krishna Bharat
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 15:07
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/951; G06F16/953; G06F16/9538; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99937
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
49 words
A method of generating documents based on a search query, comprising: obtaining an initial set of documents relevant to the search query; assigning relevance scores to the documents based on cross references between the documents within the initial set; and sorting the documents based on the assigned relevance scores.
Claim 2
Independent Claim
49 words
A method of generating documents based on a search query, comprising: obtaining an initial set of documents relevant to the search query; assigning relevance scores to the documents based on cross references between the documents within the initial set; and sorting the documents based on the assigned relevance scores.
Claim 3
Dependent Claim
91 words
The method of claim 1 , wherein the initial set of documents are associated with initial relevance scores, and wherein assigning the relevance scores includes: calculating a local score value for at least two of the documents in the initial set, the local score value quantifying an amount that the at least two documents are supported by other documents in the initial set of documents; and generating refined relevance scores for the at least two documents in the initial set based on the local score values and the initial relevance scores.
Claim 4
Dependent Claim
87 words
The method of claim 1 , wherein the initial set of documents are associated with initial relevance scores, and wherein assigning the relevance scores includes: calculating a local score value for at least two of the documents in the initial set based on the cross references to the at least two documents by other documents in the initial set of documents; and generating refined relevance scores for the at least two documents in the initial set based on the local score values and the initial relevance scores.
Claim 5
Dependent Claim
80 words
The method of claim 2 , wherein calculating the local score value for a particular one of the at least two documents in the initial set of documents further includes: forming a sub-set of documents from the initial set of documents as the sub-set of documents that cross reference the particular one of the at least two documents, and removing at least one document from the sub-set that is affiliated with the particular one of the at least two documents.
Claim 6
Dependent Claim
45 words
The method of claim 4 , further comprising: removing, for at least one pair of documents in the sub-set that are affiliated, one of the documents in the pair that has a lower initial relevance score than the other of the documents in the pair.
Claim 7
Dependent Claim
24 words
The method of claim 4 , wherein a predefined number of the documents in the sub-set are used to calculate the local score value.
Claim 8
Dependent Claim
87 words
The method of claim 4 , wherein the local score value is calculated for the particular one of the at least two documents as: ∑ i = 1 k OldScore ( BackSet ( i ) ) m where OldScore(x) refers to the initial relevance score value for one of the at least two documents, BackSet refers to the sub-set of documents, the sum is taken over the first k documents in BackSet, where k is a predefined number, and m is a predetermined constant.
Claim 9
Dependent Claim
29 words
The method of claim 2 , wherein generating the refined relevance scores is based on taking a product based on the local score values and the initial relevance scores.
Claim 10
Dependent Claim
79 words
The method of claim 2 , wherein generating the refined relevance score further includes: calculating the refined relevance scores as NewScore( x )=( a +LocalScore( x )/MaxLS)( b +OldScore( x )/MaxOS) where NewScore is the calculated refined relevance score value, a and b are predetermined constants, MaxLS is equal to the maximum of the calculated local score values, MaxOS is equal to the maximum of the calculated initial relevance score values, and LocalScore(x) refers to the local score value.
Claim 11
Dependent Claim
22 words
The method of claim 9 , further including: setting MaxLS to a predetermined threshold value when MaxLS is below the threshold value.
Claim 12
Dependent Claim
32 words
The method of claim 1 , wherein obtaining the initial set of relevant documents includes obtaining the initial set based on a matching of terms in the search query to a corpus.
Claim 13
Independent Claim
75 words
A method of responding to a search query from a user, the method comprising: receiving the search query from the user; generating a list of relevant documents based on search terms of the query; generating relevance scores for the documents in the list of relevant documents based on cross references between the documents in the list; and returning a set of relevant documents to the user, the set being sorted based on the relevance scores.
Claim 14
Independent Claim
75 words
A method of responding to a search query from a user, the method comprising: receiving the search query from the user; generating a list of relevant documents based on search terms of the query; generating relevance scores for the documents in the list of relevant documents based on cross references between the documents in the list; and returning a set of relevant documents to the user, the set being sorted based on the relevance scores.
Claim 15
Dependent Claim
97 words
The method of claim 12 , wherein generating the list of relevant documents includes determining initial relevance scores for the list of relevant documents and wherein generating the relevance scores includes: calculating a local score value for at least two of the documents in the list of relevant documents, the local score value quantifying an amount that the at least two documents are cross referenced by other documents in the list of relevant documents; and calculating refined relevance scores for the documents in the initial set based on the local score values and the initial relevance scores.
Claim 16
Dependent Claim
71 words
The method of claim 13 , wherein calculating the local score value for a particular one of the documents in the list of relevant documents further includes: forming a sub-set of documents from the list of relevant documents as the sub-set of documents that cross reference the particular one of the documents, and removing at least one document from the sub-set that is affiliated with the particular one of the documents.
Claim 17
Dependent Claim
45 words
The method of claim 14 , further comprising: removing, for at least one pair of documents in the sub-set that are affiliated, one of the documents in the pair that has a lower initial relevance score than the other of the documents in the pair.
Claim 18
Dependent Claim
24 words
The method of claim 14 , wherein a predefined number of the documents in the sub-set are used to calculate the local score value.
Claim 19
Dependent Claim
28 words
The method of claim 13 , wherein calculating the relevance scores is based on taking a product based on the local score values and the initial relevance scores.
Claim 20
Independent Claim
87 words
A system for identifying documents relevant to a search query comprising: means for obtaining an initial set of relevant documents from a corpus based on a matching of terms in the search query to the corpus; means for assigning refined relevance scores to the set of relevant documents based on an amount that the documents of the initial set are cross referenced by other documents in the initial set of documents; and means for sorting the documents in the initial set based on the refined relevance scores.
Claim 21
Independent Claim
87 words
A system for identifying documents relevant to a search query comprising: means for obtaining an initial set of relevant documents from a corpus based on a matching of terms in the search query to the corpus; means for assigning refined relevance scores to the set of relevant documents based on an amount that the documents of the initial set are cross referenced by other documents in the initial set of documents; and means for sorting the documents in the initial set based on the refined relevance scores.
Claim 22
Dependent Claim
25 words
The system of claim 18 , further comprising: means for determining an initial relevance score for each document in the initial set of relevant documents.
Claim 23
Dependent Claim
73 words
The system of claim 18 , wherein the means for assigning further includes: means for forming a sub-set of documents from the initial set of relevant documents as the sub-set of documents that cross reference a particular one of the documents in the initial set of relevant documents, and means for removing documents from the sub-set that are affiliated with the particular one of the documents in the initial set of relevant documents.
Claim 24
Dependent Claim
65 words
A computer-readable medium storing instructions for causing at least one processor to perform a method that identifies documents relevant to a search query, the method comprising: obtaining an initial set of documents relevant to the search query; assigning refined relevance scores to the documents based on cross references between the documents within the initial set; and sorting the documents based on the refined relevance scores.
Claim 25
Dependent Claim
65 words
A computer-readable medium storing instructions for causing at least one processor to perform a method that identifies documents relevant to a search query, the method comprising: obtaining an initial set of documents relevant to the search query; assigning refined relevance scores to the documents based on cross references between the documents within the initial set; and sorting the documents based on the refined relevance scores.
Claim 26
Dependent Claim
92 words
The computer-readable medium of claim 21 , wherein the initial set of documents are associated with initial relevance scores, and wherein assigning the refined relevance scores includes: calculating a local score value for at least two of the documents in the initial set, the local score value quantifying an amount that the at least two documents are cross referenced by other documents in the initial set of documents; and generating the refined relevance scores for the documents in the initial set based on the local score values and the initial relevance scores.
Claim 27
Dependent Claim
76 words
The computer-readable medium of claim 21 , wherein calculating the local score value for a particular one of the initial set of documents further includes: forming a sub-set of documents from the initial set of documents as the sub-set of documents that contain a hyperlink to the particular one of the documents, and removing documents from the sub-set that are from a same host or from an affiliated host as the particular one of the documents.
Claim 28
Dependent Claim
43 words
The computer-readable medium of claim 23 , further comprising: removing, for pairs of documents in the sub-set that are affiliated, one of the documents in the pair that has a lower refined relevance score than the other of the documents in the pair.
Claim 29
Dependent Claim
25 words
The computer-readable medium of claim 23 , wherein a predefined number of the documents in the sub-set are used to calculate the local score value.
Claim 30
Dependent Claim
33 words
The computer-readable medium of claim 23 , wherein obtaining the initial set of relevant documents includes obtaining the initial set based on a matching of terms in the search query to a corpus.
Claim 31
Dependent Claim
12 words
The method of claim 1 , wherein the cross references are hyperlinks.
Claim 32
Dependent Claim
12 words
The method of claim 12 , wherein the cross references are hyperlinks.
Claim 33
Dependent Claim
12 words
The system of claim 18 , wherein the cross references are hyperlinks.
Claim 34
Dependent Claim
13 words
The computer-readable medium of claim 21 , wherein the cross references are hyperlinks.
References Cited (Backward Citations)
US5913208A
Cited
US6070158A
Cited
US6119114A
Cited
US5870740A
Cited
US5920859A
Cited
US5907840A
Cited
US6263329B1
Cited
US6286000B1
Cited
US6546388B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-04-20 | 2007-10-20 | 2008-04-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-04-20 | 2011-10-20 | 2012-04-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-04-20 | 2015-10-20 | 2016-04-20 | $7700.00 | Window Closed / Lapsed |