Method and apparatus for predicting document access in a collection of linked documents featuring link proprabilities and spreading activation

• US 6,115,718 A
• Filed: 04/01/1998
• Issued: 09/05/2000
• Est. Priority Date: 04/01/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Pirolli, Peter L., Pitkow, James E., Huberman, Bernardo A.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): TRINH, WILLIAM B
• Application Number:
  US09/053,616
• Time in Patent Office: 888 Days
• Field of Search: 707/102, 707/501, 707/513
• US Class Current: 1/1
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.