US6601075B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method of ranking and retrieving documents based on authority scores of schemas and documents
Assignee: Google LLC
•
Filing: 2000-07-27
•
Granted: 2003-07-29
•
Expires: 2020-07-27
Abstract
Abstract The ranking manager and associated method of the present invention rank the authority of XML documents and their corresponding schemas using an iterative process over a set of hyperlinked XML documents and their schemas. The ranking manager introduces the notion of authoritative schemas and document structure, and maintains an authority score for each document in the set, a hub score for each document in the set, and an authority score for each schema that is used by one or more documents in the set. The ranking manager initializes these scores according to predefined criteria, and then recomputes in successive iterations: (1) the authority scores for each schema based on the hub scores of the documents that use the schema and the authority scores of the documents that use the schema, (2) the authority scores for each document based on the authority score for the schema that it uses and the hub scores of the documents that point to it, and/or (3) the hub scores for each document in the set based on the authority score for the schema that it uses and the authority scores of the documents that it points to. The ranking manager performs these computations until convergence or a threshold value of difference is reached.
Inventors
- 👤 Anita Wai-Ling Huang
- 👤 Neelakantan Sundaresan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 05:30
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/951; G06F16/953; G06F16/9538; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
239 words
A method for retrieving documents and associated schemas, comprising: retrieving a seed set of documents with a hyperlinked structure, and associated schemas; maintaining a hub score, h(d), and an authority score, a(d), for each document of the seed set, and an authority score a(s) for each schema used by one or more documents in the set; initializing the hub score, h(d), the authority score, a(d), and the authority score a(s) to respective predefined criteria; and iteratively recomputing any one or more of: the authority score a(s) for each schema based on the hub scores h(d) of the documents that use the schema and the authority scores a(d) of the documents that use the schema; the authority scores a(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the hub scores (d) of the documents that point to said each document; or the hub scores h(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the authority scores a(d) of the documents that said each document points to; ordering the documents according to any one or more of the authority score a(d) or the hub score h(d) of the documents, ordering the schemas according to the authority score a(s) of the schemas, returning an ordered set of documents from the seed set of documents.
Claim 2
Independent Claim
239 words
A method for retrieving documents and associated schemas, comprising: retrieving a seed set of documents with a hyperlinked structure, and associated schemas; maintaining a hub score, h(d), and an authority score, a(d), for each document of the seed set, and an authority score a(s) for each schema used by one or more documents in the set; initializing the hub score, h(d), the authority score, a(d), and the authority score a(s) to respective predefined criteria; and iteratively recomputing any one or more of: the authority score a(s) for each schema based on the hub scores h(d) of the documents that use the schema and the authority scores a(d) of the documents that use the schema; the authority scores a(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the hub scores (d) of the documents that point to said each document; or the hub scores h(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the authority scores a(d) of the documents that said each document points to; ordering the documents according to any one or more of the authority score a(d) or the hub score h(d) of the documents, ordering the schemas according to the authority score a(s) of the schemas, returning an ordered set of documents from the seed set of documents.
Claim 3
Dependent Claim
32 words
The method of claim 1 , further including computing corresponding weights to the hub score, h(d), and the authority score, a(d), of said document based on a structure of said each document.
Claim 4
Dependent Claim
32 words
The method of claim 2 , wherein computing corresponding weights includes computing weights to the hub score, h(d), and the authority score, a(d), of said document based on document validity, and well-formedness.
Claim 5
Dependent Claim
28 words
The method of claim 1 , wherein iteratively recomputing including recomputing the authority score a(s), the authority scores a(d), and the hub scores h(d) until convergence is reached.
Claim 6
Dependent Claim
32 words
The method of claim 1 , wherein iteratively recomputing including recomputing the authority score a(s), the authority scores a(d), and the hub scores h(d) until a threshold value of difference is reached.
Claim 7
Dependent Claim
34 words
The method of claim 4 , further including ranking the documents in the set and the associated schemas according to the recomputed authority score a(s), the authority scores a(d), and the hub scores h(d).
Claim 8
Dependent Claim
34 words
The method of claim 5 , further including ranking the documents in the set and the associated schemas according to the recomputed authority score a(s), the authority scores a(d), and the hub scores h(d).
Claim 9
Independent Claim
184 words
A method for ranking a set of documents, d, with a hyperlinked structure, and associated schemas, comprising: maintaining a hub score, h(d), and an authority score, a(d), for each document, d, and an authority score a(s) for each schema used by one or more documents in the set; initializing the hub score, h(d), the authority score, a(d), and the authority score a(s) to respective predefined criteria; and iteratively recomputing any one or more of: the authority score a(s) for each schema based on the hub scores h(d) of the documents that use the schema and the authority scores a(d) of the documents that use the schema; the authority scores a(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the hub scores (d) of the documents that point to said each document; the hub scores h(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the authority scores a(d) of the documents that said each document points to.
Claim 10
Independent Claim
184 words
A method for ranking a set of documents, d, with a hyperlinked structure, and associated schemas, comprising: maintaining a hub score, h(d), and an authority score, a(d), for each document, d, and an authority score a(s) for each schema used by one or more documents in the set; initializing the hub score, h(d), the authority score, a(d), and the authority score a(s) to respective predefined criteria; and iteratively recomputing any one or more of: the authority score a(s) for each schema based on the hub scores h(d) of the documents that use the schema and the authority scores a(d) of the documents that use the schema; the authority scores a(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the hub scores (d) of the documents that point to said each document; the hub scores h(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the authority scores a(d) of the documents that said each document points to.
Claim 11
Dependent Claim
32 words
The method of claim 8 , further including computing corresponding weights to the hub score, h(d), and the authority score, a(d), of said document based on a structure of said each document.
Claim 12
Dependent Claim
32 words
The method of claim 9 , wherein computing corresponding weights includes computing weights to the hub score, h(d), and the authority score, a(d), of said document based on document validity, and well-formedness.
Claim 13
Dependent Claim
55 words
The method of claim 9 , wherein iteratively recomputing including recomputing the authority score a(s), the authority scores a(d), and the hub scores h(d) until convergence is reached; and ranking the documents in the set and the associated schemas according to the recomputed authority score a(s), the authority scores a(d), and the hub scores h(d).
Claim 14
Dependent Claim
59 words
The method of claim 9 , wherein iteratively recomputing including recomputing the authority score a(s), the authority scores a(d), and the hub scores h(d) until a threshold value of difference is reached; and ranking the documents in the set and the associated schemas according to the recomputed authority score a(s), the authority scores a(d), and the hub scores h(d).
Claim 15
Independent Claim
194 words
A system for retrieving a set of documents, d, with a hyperlinked structure, and associated schemas, comprising: a ranking module for maintaining a hub score, h(d), and an authority score, a(d), for each document, d, and an authority score a(s) for each schema used by one or more documents in the set; the ranking manager initializing the hub score, h(d), the authority score, a(d), and the authority score a(s) to respective predefined criteria; and the ranking module iteratively recomputing any one or more of: the authority score a(s) for each schema based on the hub scores h(d) of the documents that use the schema and the authority scores a(d) of the documents that use the schema; the authority scores a(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the hub scores (d) of the documents that point to said each document; the hub scores h(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the authority scores a(d) of the documents that said each document points to.
Claim 16
Independent Claim
194 words
A system for retrieving a set of documents, d, with a hyperlinked structure, and associated schemas, comprising: a ranking module for maintaining a hub score, h(d), and an authority score, a(d), for each document, d, and an authority score a(s) for each schema used by one or more documents in the set; the ranking manager initializing the hub score, h(d), the authority score, a(d), and the authority score a(s) to respective predefined criteria; and the ranking module iteratively recomputing any one or more of: the authority score a(s) for each schema based on the hub scores h(d) of the documents that use the schema and the authority scores a(d) of the documents that use the schema; the authority scores a(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the hub scores (d) of the documents that point to said each document; the hub scores h(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the authority scores a(d) of the documents that said each document points to.
Claim 17
Dependent Claim
35 words
The system of claim 13 , wherein the ranking manager further computes corresponding weights to the hub score, h(d), and the authority score, a(d), of said document based on a structure of said each document.
Claim 18
Dependent Claim
14 words
The method of claim 14 , wherein the set of documents include XML documents.
Claim 19
Dependent Claim
59 words
The method of claim 14 , wherein the ranking manager iteratively recomputes the authority score a(s), the authority scores a(d), and the hub scores h(d) until convergence is reached; and the ranking manager ranks the documents in the set and the associated schemas according to the recomputed authority score a(s), the authority scores a(d), and the hub scores h(d).
Claim 20
Dependent Claim
63 words
The method of claim 14 , wherein the ranking manager iteratively recomputes the authority score a(s), the authority scores a(d), and the hub scores h(d) until a threshold value of difference is reached; and the ranking manager ranks the documents in the set and the associated schemas according to the recomputed authority score a(s), the authority scores a(d), and the hub scores h(d).
Claim 21
Dependent Claim
196 words
A computer software product for ranking a set of documents, d, with a hyperlinked structure, and associated schemas, comprising: a ranking module for maintaining a hub score, h(d), and an authority score, a(d), for each document, d, and an authority score a(s) for each schema used by one or more documents in the set; the ranking manager initializing the hub score, h(d), the authority score, a(d), and the authority score a(s) to respective predefined criteria; and the ranking module iteratively recomputing any one or more of: the authority score a(s) for each schema based on the hub scores h(d) of the documents that use the schema and the authority scores a(d) of the documents that use the schema; the authority scores a(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the hub scores (d) of the documents that point to said each document; the hub scores h(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the authority scores a(d) of the documents that said each document points to.
Claim 22
Dependent Claim
196 words
A computer software product for ranking a set of documents, d, with a hyperlinked structure, and associated schemas, comprising: a ranking module for maintaining a hub score, h(d), and an authority score, a(d), for each document, d, and an authority score a(s) for each schema used by one or more documents in the set; the ranking manager initializing the hub score, h(d), the authority score, a(d), and the authority score a(s) to respective predefined criteria; and the ranking module iteratively recomputing any one or more of: the authority score a(s) for each schema based on the hub scores h(d) of the documents that use the schema and the authority scores a(d) of the documents that use the schema; the authority scores a(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the hub scores (d) of the documents that point to said each document; the hub scores h(d) for said each document in the set based on the authority score a(s) for the schema used by said each document and the authority scores a(d) of the documents that said each document points to.
Claim 23
Dependent Claim
37 words
The computer software product of claim 18 , wherein the ranking manager further computes corresponding weights to the hub score, h(d), and the authority score, a(d), of said document based on a structure of said each document.
Claim 24
Dependent Claim
82 words
The computer software product of claim 19 , wherein the set of documents include XML documents; wherein the ranking manager iteratively recomputes the authority score a(s), the authority scores a(d), and the hub scores h(d) any one or more conditions is satisfied: convergence is reached or threshold value of difference is reached; and the ranking manager ranks the documents in the set and the associated schemas according to the recomputed authority score a(s), the authority scores a(d), and the hub scores h(d).
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-07-28 | 2007-01-27 | 2007-07-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-07-28 | 2011-01-27 | 2011-07-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-07-28 | 2015-01-27 | 2015-07-29 | $7700.00 | Window Closed / Lapsed |