US6115718A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for predicting document access in a collection of linked documents featuring link proprabilities and spreading activation
Assignee: Xerox Corp
•
Filing: 1998-04-01
•
Granted: 2000-09-05
•
Expires: 2018-04-01
Abstract
Abstract A method and apparatus for predicting document access within a collection of linked documents. The present invention utilizes a predictive technique known as "spreading activation" where document collections are graphically represented as a network. Empirical data is analyzed according to a law of surfing to generate a decay function which is used to dampen the activation as spreads through the network. Activation is applied to a set of focus documents and propagates through the network until a stable pattern of activation is achieved across all documents. From this stable pattern, the desired usage information is extracted. Such a system will provide several practical benefits to users of the World Wide Web. For example, the present invention can be used to identify relevant pages to a set of one or more focus pages or to predict the number of times a document will be accessed in a collection of linked documents. Further, alone or in combination, this information can be used in connection with web site design or re-design.
Inventors
- 👤 Bernardo A. Huberman
- 👤 James E. Pitkow
- 👤 Peter L. Pirolli
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 22:24
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/951; G06F16/93; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
174 words
A method for predicting document access within a collection of linked documents comprising the steps of: a) gathering usage data for said collection of linked documents; b) generating initial activation information, said initial activation information indicating a set of focus documents in said collection of linked documents; c) generating page to page transition information from said usage data, said page to page transition information indicating a strength of association between documents in said collection of linked documents; d) generating link probability information from said usage data, said link probability information indicating a distribution of the number of documents a user will access in said collection of linked documents; e) performing a spreading activation operation based on said initial activation information, page to page transition information and said probability information based on a network representation of said collection of linked documents; and f) extracting said document access information resulting from said spreading activation step when a stable pattern of activation across all nodes of said network representation of said collection of linked documents is reached.
Claim 2
Independent Claim
174 words
A method for predicting document access within a collection of linked documents comprising the steps of: a) gathering usage data for said collection of linked documents; b) generating initial activation information, said initial activation information indicating a set of focus documents in said collection of linked documents; c) generating page to page transition information from said usage data, said page to page transition information indicating a strength of association between documents in said collection of linked documents; d) generating link probability information from said usage data, said link probability information indicating a distribution of the number of documents a user will access in said collection of linked documents; e) performing a spreading activation operation based on said initial activation information, page to page transition information and said probability information based on a network representation of said collection of linked documents; and f) extracting said document access information resulting from said spreading activation step when a stable pattern of activation across all nodes of said network representation of said collection of linked documents is reached.
Claim 3
Dependent Claim
58 words
The method as recited in claim 1 wherein said step of generating link probability information from said usage data is further comprised of the step of generating mean and standard deviation values for the number of document accesses made by all users in said document collection, said mean and standard deviation values based on an inverse Gaussian distribution.
Claim 4
Dependent Claim
44 words
The method as recited in claim 1 wherein said step of performing a spreading activation operation is further comprised of the step of using said link probability information as a dampening factor for activation across said network representation of said collection of linked documents.
Claim 5
Independent Claim
137 words
A method for modeling document access in a collection of linked documents based on prior usage information of said collection, said method comprising the steps of: a) generating an initial activation matrix, said initial activation matrix indicating a set of focus documents in said collection of linked documents; b) generating a transition matrix using said prior usage information, said transition matrix indicating user traversal information between documents in said collection of link ed documents; c) generating a link probability vector from said prior usage information, said link probability vector indicating probabilities that a user will link to another document in said document collection; d) performing a spreading activation operation using said initial activation matrix, transition matrix and link probability vector to obtain a spreading activation result; and e) extracting document access information from said spreading activation result.
Claim 6
Independent Claim
137 words
A method for modeling document access in a collection of linked documents based on prior usage information of said collection, said method comprising the steps of: a) generating an initial activation matrix, said initial activation matrix indicating a set of focus documents in said collection of linked documents; b) generating a transition matrix using said prior usage information, said transition matrix indicating user traversal information between documents in said collection of link ed documents; c) generating a link probability vector from said prior usage information, said link probability vector indicating probabilities that a user will link to another document in said document collection; d) performing a spreading activation operation using said initial activation matrix, transition matrix and link probability vector to obtain a spreading activation result; and e) extracting document access information from said spreading activation result.
Claim 7
Dependent Claim
59 words
The method as recited in claim 4 wherein said step of generating a link probability vector from said prior usage information is further comprised of the step generating mean and standard deviation values for the number of document accesses made by all users in said document collection, said mean and standard deviation values based on an inverse Gaussian distribution.
Claim 8
Dependent Claim
31 words
The method as recited in claim 4 wherein said step of performing a spreading activation operation is further comprised of the step of using said link probability vector to dampen activation.
Claim 9
Independent Claim
181 words
A system for predicting document access within a collection of linked documents comprising: means for gathering usage data for said collection of linked documents; means for generating initial activation information, said initial activation information indicating a set of focus documents in said collection of linked documents; means for generating page to page transition information from said usage data, said page to page transition information indicating a strength of association between documents in said collection of linked documents; means for generating link probability information from said usage data, said link probability information indicating a distribution of the number of documents a user will access in said collection of linked documents; spreading activation means for performing a spreading activation operation based on said initial activation information, page to page transition information and said probability information based on a network representation of said collection of linked documents; and information extraction means for extracting said document access information resulting from said spreading activation step when a stable pattern of activation across all nodes of said network representation of said collection of linked documents is reached.
Claim 10
Independent Claim
181 words
A system for predicting document access within a collection of linked documents comprising: means for gathering usage data for said collection of linked documents; means for generating initial activation information, said initial activation information indicating a set of focus documents in said collection of linked documents; means for generating page to page transition information from said usage data, said page to page transition information indicating a strength of association between documents in said collection of linked documents; means for generating link probability information from said usage data, said link probability information indicating a distribution of the number of documents a user will access in said collection of linked documents; spreading activation means for performing a spreading activation operation based on said initial activation information, page to page transition information and said probability information based on a network representation of said collection of linked documents; and information extraction means for extracting said document access information resulting from said spreading activation step when a stable pattern of activation across all nodes of said network representation of said collection of linked documents is reached.
Claim 11
Dependent Claim
55 words
The system as recited in claim 7 wherein said means for generating link probability information is further comprised of statistics generation means for generating mean and standard deviation values for the number of document accesses made by all users in said document collection, said mean and standard deviation values based on an inverse Gaussian distribution.
References Cited (Backward Citations)
US5305389A
Cited
US5418948A
Cited
US5754939A
Cited
US5668988A
Cited
US5842199A
Cited
US5835905A
Cited
US5878223A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-09-05 | 2004-03-06 | 2004-09-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-09-05 | 2008-03-06 | 2008-09-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-09-05 | 2012-03-06 | 2012-09-05 | $7700.00 | Window Closed / Lapsed |