US6112202A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for identifying authoritative information resources in an environment with content-based links between information resources
Assignee: International Business Machines Corp
•
Filing: 1997-03-07
•
Granted: 2000-08-29
•
Expires: 2017-03-07
Abstract
Abstract A system and method are provided for searching for desired items from a network of information resources. In particular, the system and method have advantageous applicability to searching for World Wide Web pages having desired content. An initial set of pages are selected, preferably by running a conventional keyword-based query, and then further selecting pages pointing to, or pointed to from, the pages found by the keyword-based query. Alternatively, the invention may be applied to a single page, where the initial set includes pages pointed to by the single page and pages which point to the single page. Then, iteratively, authoritativeness values are computed for the pages of the initial set, based on the number of links to and from the pages. One or more communities, or "neighborhoods", of related pages are defined based on the authoritativeness values thus produced. Such communities of pages are likely to be of particular interest and value to the user who is interested in the keyword-based query or the single page.
Inventors
- 👤 Jon Michael Kleinberg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 15:02
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/951; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99939; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 60
Claim 1
Independent Claim
188 words
A computer program product, for use with a computer system, for directing the computer system to execute a search of information resources, the resources having content-based links between each other, to identify a desired subset of the information resources which satisfy a desired criterion, the computer program product comprising: a computer-readable medium; means, provided on the recording medium, for directing the computer system to identify an initial set of information resources; means, provided on the recording medium, for directing the computer system to define initial authoritativeness information for the initial set; means, provided on the recording medium, for directing the computer system to use the initial authoritativeness information as input authoritativeness information, to execute the steps of: (i) producing first authoritativeness information about a set of information resources pointed to by links in resources of the input set, and (ii) producing second authoritativeness information about a set of information resources having links that point to resources of the input set; and means, provided on the recording medium, for directing the computer system to produce a final set of information resources based on the first and second authoritativeness information.
Claim 2
Dependent Claim
188 words
A computer program product, for use with a computer system, for directing the computer system to execute a search of information resources, the resources having content-based links between each other, to identify a desired subset of the information resources which satisfy a desired criterion, the computer program product comprising: a computer-readable medium; means, provided on the recording medium, for directing the computer system to identify an initial set of information resources; means, provided on the recording medium, for directing the computer system to define initial authoritativeness information for the initial set; means, provided on the recording medium, for directing the computer system to use the initial authoritativeness information as input authoritativeness information, to execute the steps of: (i) producing first authoritativeness information about a set of information resources pointed to by links in resources of the input set, and (ii) producing second authoritativeness information about a set of information resources having links that point to resources of the input set; and means, provided on the recording medium, for directing the computer system to produce a final set of information resources based on the first and second authoritativeness information.
Claim 3
Dependent Claim
24 words
A computer program product as recited in claim 1, wherein the information resources include World Wide Web pages, and the content-based links include hyperlinks.
Claim 4
Dependent Claim
47 words
A computer program product as recited in claim 1, wherein the means for directing to identify an initial set of information resources includes means, provided on the recording medium, for directing the computer system to obtain, as an input, an information resource containing subject matter of interest.
Claim 5
Dependent Claim
48 words
A computer program product as recited in claim 3, wherein the means for directing to identify an initial set of information resources includes means, provided on the recording medium, for directing the computer system to identify a further set of information resources linked to the input information resource.
Claim 6
Dependent Claim
83 words
A computer program product as recited in claim 1, wherein: the means for directing to execute the steps of producing first and second authoritativeness information is operative in a series of iterations; the initial authoritativeness information is used as input authoritativeness information for a first iteration; and the produced first and second authoritativeness information is a result of the iteration, the first and second authoritativeness information produced in a given iteration to be used as the input authoritativeness information for the next iteration.
Claim 7
Dependent Claim
47 words
A computer program product as recited in claim 1 further comprising means, provided on the recording medium, for directing the computer system to execute the steps of producing first authoritativeness information and producing second authoritativeness information in a series of iterations until a predetermined condition is met.
Claim 8
Dependent Claim
22 words
A computer program product as recited in claim 6, wherein the predetermined condition includes the execution of a specified number of iterations.
Claim 9
Dependent Claim
27 words
A computer program product as recited in claim 6, wherein the predetermined condition includes a steady state in which further iterations result in substantially the same results.
Claim 10
Dependent Claim
54 words
A computer program product as recited in claim 6, wherein the means for directing to identify an initial set of information resources includes means, provided on the recording medium, for directing the computer system to execute a keyword-based query search, results of the search including information resources to be included in the initial set.
Claim 11
Dependent Claim
65 words
A computer program product as recited in claim 9, wherein the means for directing to identify an initial set of information resources further includes means, provided on the recording medium, for directing the computer system to identify information resources linked to or from the information resources which are the results of the search, the former information resources also to be included in the initial set.
Claim 12
Dependent Claim
48 words
A computer program product as recited in claim 10, wherein the means for directing to define initial authoritativeness information includes means, provided on the recording medium, for directing the computer system to select an initial numerical authoritativeness value for each of the information resources of the initial set.
Claim 13
Dependent Claim
51 words
A computer program product as recited in claim 11, wherein the means for directing to define initial authoritativeness information further includes means, provided on the recording medium, for directing the computer system to define an authority value and a hub value for each of the information resources of the initial set.
Claim 14
Dependent Claim
59 words
A computer program product as recited in claim 12, wherein the defined authority values and hub values are processed as vectors, each vector containing a respective term corresponding with each respective one of the information resources of the initial set, and having stored therein the value defined for that respective one of the information resources of the initial set.
Claim 15
Dependent Claim
63 words
A computer program product as recited in claim 12, wherein: an initial hub value is defined as 1 if the information resource was found by the keyword-based query search, and 0 if the information resource is linked to or from the information resources which are the results of the search; and an initial authority value is defined as 0 for all information resources.
Claim 16
Dependent Claim
69 words
A computer program product as recited in claim 12, wherein, for each iteration: the hub value for an information resource is updated as the sum of the authority values for authority information resources which point to the hub information resource; and the authority value for an information resource is updated as the sum of the hub values for hub information resources which are pointed to by the information resource.
Claim 17
Dependent Claim
24 words
A computer program product as recited in claim 15, wherein each iteration further includes normalizing the hub and authority values for the information resources.
Claim 18
Dependent Claim
48 words
A computer program product as recited in claim 1, wherein the means for directing to produce a final set of information resources includes means, provided on the recording medium, for directing the computer system to select information resources from the set based on their hub and authority values.
Claim 19
Dependent Claim
41 words
A computer program product as recited in claim 17, wherein the means for directing to select includes means, provided on the recording medium, for directing the computer system to select information resources whose hub values or authority values have greatest magnitudes.
Claim 20
Dependent Claim
63 words
A computer program product as recited in claim 17, wherein the means for directing to select includes means, provided on the recording medium, for directing the computer system to select a plurality of successive communities, selecting each successive community including selecting information resources whose hub values or authority values have greatest magnitudes of those information resources not already selected for a prior community.
Claim 21
Independent Claim
124 words
A method for executing a search of information resources, the resources having content-based links between each other, to identify a desired subset of the information resources which satisfy a desired criterion, the method comprising the steps of: identifying an initial set of information resources; defining initial authoritativeness information for the initial set; using the initial authoritativeness information as input authoritativeness information, executing the steps of: (i) producing first authoritativeness information about a set of information resources pointed to by links in resources of the input set, and (ii) producing second authoritativeness information about a set of information resources having links that point to resources of the input set; and producing a final set of information resources based on the first and second authoritativeness information.
Claim 22
Independent Claim
124 words
A method for executing a search of information resources, the resources having content-based links between each other, to identify a desired subset of the information resources which satisfy a desired criterion, the method comprising the steps of: identifying an initial set of information resources; defining initial authoritativeness information for the initial set; using the initial authoritativeness information as input authoritativeness information, executing the steps of: (i) producing first authoritativeness information about a set of information resources pointed to by links in resources of the input set, and (ii) producing second authoritativeness information about a set of information resources having links that point to resources of the input set; and producing a final set of information resources based on the first and second authoritativeness information.
Claim 23
Dependent Claim
22 words
A method as recited in claim 20, wherein the information resources include World Wide Web pages, and the content-based links include hyperlinks.
Claim 24
Dependent Claim
31 words
A method as recited in claim 20, wherein the step of identifying an initial set of information resources includes obtaining, as an input, an information resource containing subject matter of interest.
Claim 25
Dependent Claim
32 words
A method as recited in claim 22, wherein the step of identifying an initial set of information resources includes identifying a further set of information resources linked to the input information resource.
Claim 26
Dependent Claim
79 words
A method as recited in claim 20, wherein: the step of executing the steps of producing first and second authoritativeness information is executed in a series of iterations; the initial authoritativeness information is used as input authoritativeness information for a first iteration; and the produced first and second authoritativeness information is a result of the iteration, the first and second authoritativeness information produced in a given iteration to be used as the input authoritativeness information for the next iteration.
Claim 27
Dependent Claim
33 words
A method as recited in claim 20, wherein the steps of producing first authoritativeness information and producing second authoritativeness information are executed in a series of iterations until a predetermined condition is met.
Claim 28
Dependent Claim
20 words
A method as recited in claim 25, wherein the predetermined condition includes the execution of a specified number of iterations.
Claim 29
Dependent Claim
25 words
A method as recited in claim 25, wherein the predetermined condition includes a steady state in which further iterations result in substantially the same results.
Claim 30
Dependent Claim
38 words
A method as recited in claim 25, wherein the step of identifying an initial set of information resources includes executing a keyword-based query search, results of the search including information resources to be included in the initial set.
Claim 31
Dependent Claim
49 words
A method as recited in claim 28, wherein the step of identifying an initial set of information resources further includes identifying information resources linked to or from the information resources which are the results of the search, the former information resources also to be included in the initial set.
Claim 32
Dependent Claim
32 words
A method as recited in claim 29, wherein the step of defining initial authoritativeness information includes selecting an initial numerical authoritativeness value for each of the information resources of the initial set.
Claim 33
Dependent Claim
35 words
A method as recited in claim 30, wherein the step of defining initial authoritativeness information further includes defining an authority value and a hub value for each of the information resources of the initial set.
Claim 34
Dependent Claim
57 words
A method as recited in claim 31, wherein the defined authority values and hub values are processed as vectors, each vector containing a respective term corresponding with each respective one of the information resources of the initial set, and having stored therein the value defined for that respective one of the information resources of the initial set.
Claim 35
Dependent Claim
61 words
A method as recited in claim 31, wherein: an initial hub value is defined as 1 if the information resource was found by the keyword-based query search, and 0 if the information resource is linked to or from the information resources which are the results of the search; and an initial authority value is defined as 0 for all information resources.
Claim 36
Dependent Claim
67 words
A method as recited in claim 31, wherein, for each iteration: the hub value for an information resource is updated as the sum of the authority values for authority information resources which point to the hub information resource; and the authority value for an information resource is updated as the sum of the hub values for hub information resources which are pointed to by the information resource.
Claim 37
Dependent Claim
22 words
A method as recited in claim 34, wherein each iteration further includes normalizing the hub and authority values for the information resources.
Claim 38
Dependent Claim
46 words
A method as recited in claim 20, wherein: each information resource is associated with an authority value and a hub value; and the step of producing a final set of information resources includes selecting information resources from the set based on the hub and authority values.
Claim 39
Dependent Claim
25 words
A method as recited in claim 36, wherein the step of selecting includes selecting information resources whose hub values or authority values have greatest magnitudes.
Claim 40
Dependent Claim
47 words
A method as recited in claim 36, wherein the step of selecting includes selecting a plurality of successive communities, selecting each successive community including selecting information resources whose hub values or authority values have greatest magnitudes of those information resources not already selected for a prior community.
Claim 41
Independent Claim
130 words
A system for executing a search of information resources, the resources having content-based links between each other, to identify a desired subset of the information resources which satisfy a desired criterion, the system comprising: means for identifying an initial set of information resources; means for defining initial authoritativeness information for the initial set; means for using the initial authoritativeness information as input authoritativeness information, to execute the steps of: (i) producing first authoritativeness information about a set of information resources pointed to by links in resources of the input set, and (ii) producing second authoritativeness information about a set of information resources having links that point to resources of the input set; and means for producing a final set of information resources based on the first and second authoritativeness information.
Claim 42
Independent Claim
130 words
A system for executing a search of information resources, the resources having content-based links between each other, to identify a desired subset of the information resources which satisfy a desired criterion, the system comprising: means for identifying an initial set of information resources; means for defining initial authoritativeness information for the initial set; means for using the initial authoritativeness information as input authoritativeness information, to execute the steps of: (i) producing first authoritativeness information about a set of information resources pointed to by links in resources of the input set, and (ii) producing second authoritativeness information about a set of information resources having links that point to resources of the input set; and means for producing a final set of information resources based on the first and second authoritativeness information.
Claim 43
Dependent Claim
22 words
A system as recited in claim 39, wherein the information resources include World Wide Web pages, and the content-based links include hyperlinks.
Claim 44
Dependent Claim
33 words
A system as recited in claim 39, wherein the means for identifying an initial set of information resources includes means for obtaining, as an input, an information resource containing subject matter of interest.
Claim 45
Dependent Claim
34 words
A system as recited in claim 41, wherein the means for identifying an initial set of information resources includes means for identifying a further set of information resources linked to the input information resource.
Claim 46
Dependent Claim
79 words
A system as recited in claim 39, wherein: the means for executing the steps of producing first and second authoritativeness information is operative in a series of iterations; the initial authoritativeness information is used as input authoritativeness information for a first iteration; and the produced first and second authoritativeness information is a result of the iteration, the first and second authoritativeness information produced in a given iteration to be used as the input authoritativeness information for the next iteration.
Claim 47
Dependent Claim
35 words
A system as recited in claim 39 further comprising means for executing the steps of producing first authoritativeness information and producing second authoritativeness information in a series of iterations until a predetermined condition is met.
Claim 48
Dependent Claim
20 words
A system as recited in claim 44, wherein the predetermined condition includes the execution of a specified number of iterations.
Claim 49
Dependent Claim
25 words
A system as recited in claim 44, wherein the predetermined condition includes a steady state in which further iterations result in substantially the same results.
Claim 50
Dependent Claim
40 words
A system as recited in claim 44, wherein the means for identifying an initial set of information resources includes means for executing a keyword-based query search, results of the search including information resources to be included in the initial set.
Claim 51
Dependent Claim
51 words
A system as recited in claim 47, wherein the means for identifying an initial set of information resources further includes means for identifying information resources linked to or from the information resources which are the results of the search, the former information resources also to be included in the initial set.
Claim 52
Dependent Claim
34 words
A system as recited in claim 48, wherein the means for defining initial authoritativeness information includes means for selecting an initial numerical authoritativeness value for each of the information resources of the initial set.
Claim 53
Dependent Claim
37 words
A system as recited in claim 49, wherein the means for defining initial authoritativeness information further includes means for defining an authority value and a hub value for each of the information resources of the initial set.
Claim 54
Dependent Claim
57 words
A system as recited in claim 50, wherein the defined authority values and hub values are processed as vectors, each vector containing a respective term corresponding with each respective one of the information resources of the initial set, and having stored therein the value defined for that respective one of the information resources of the initial set.
Claim 55
Dependent Claim
61 words
A system as recited in claim 50, wherein: an initial hub value is defined as 1 if the information resource was found by the keyword-based query search, and 0 if the information resource is linked to or from the information resources which are the results of the search; and an initial authority value is defined as 0 for all information resources.
Claim 56
Dependent Claim
67 words
A system as recited in claim 50, wherein, for each iteration: the hub value for an information resource is updated as the sum of the authority values for authority information resources which point to the hub information resource; and the authority value for an information resource is updated as the sum of the hub values for hub information resources which are pointed to by the information resource.
Claim 57
Dependent Claim
22 words
A system as recited in claim 53, wherein each iteration further includes normalizing the hub and authority values for the information resources.
Claim 58
Dependent Claim
34 words
A system as recited in claim 39, wherein the means for producing a final set of information resources includes means for selecting information resources from the set based on their hub and authority values.
Claim 59
Dependent Claim
27 words
A system as recited in claim 55, wherein the means for selecting includes means for selecting information resources whose hub values or authority values have greatest magnitudes.
Claim 60
Dependent Claim
49 words
A system as recited in claim 55, wherein the means for selecting includes means for selecting a plurality of successive communities, selecting each successive community including selecting information resources whose hub values or authority values have greatest magnitudes of those information resources not already selected for a prior community.
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) | 2003-08-29 | 2004-02-28 | 2004-08-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-08-29 | 2008-02-28 | 2008-08-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-08-29 | 2012-02-28 | 2012-08-29 | $7700.00 | Window Closed / Lapsed |