System for ranking search results from a collection of documents using spreading activation techniques

• US 6,272,507 B1
• Filed: 09/29/1998
• Issued: 08/07/2001
• Est. Priority Date: 04/09/1997
• Status: Expired due to Term

• Current Assignee: Majandro LLC (IP Edge LLC)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Pirolli, Peter L., Pitkow, James E., Huberman, Bernardo A.
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): Robinson, David J
• Application Number:
  US09/163,595
• Time in Patent Office: 1,043 Days
• Field of Search: 707/5, 707/513, 707/501, 707/514, 707/529, 345/968
• US Class Current: 715/206
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A system and method for ranking the results of a search on a collection of linked documents. Documents found on the Web are typically referred to as Web pages. The system utilizes various information relating to the collection of linked documents, including the topology, content and historical usage of the linked collections of documents. The ranking is based on historical patterns and information about the current context of interest (e.g. what the user or group seems to be currently interested in doing). A spreading activation technique is used to identify the frequency of activation of the documents in the search results. Spreading activation techniques are based on representations of Web pages as nodes in graph networks representing usage, content, and hypertext relations among Web pages. After performing the spreading activation based on an initial set defined by the search results, each document from the results may be ranked based on their level of activation.

Claims

1. A method for ranking the results of a search on a collection of linked documents, said method comprising the steps of:

a) generating historical information for said collection of linked documents, its links, access and traversal patterns through said collection of linked documents;

b) providing said search results as initial activation information, said initial activation information indicating a set of focus documents for said collection of linked documents;

c) performing a spreading activation operation based on said initial activation information and said historical information and based on a network representation of said collection of linked documents;

c) extracting activation information resulting from said spreading activation operation step when a stable pattern of activation across all nodes of said network representation of said collection of linked documents is reached; and

d) ranking said search results based on said activation information, said ranking based on the level of activation achieved by documents in said search results.

2. The method as recited in claim 1 wherein said step of generating historical information for said collection of linked documents, its links, access and traversal patterns through said collection of linked documents is further comprised of the steps of:

a1) gathering usage data for said collection of linked documents;

a2) 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; and

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

3. The method as recited in claim 2 further comprising the step of:

e) presenting said ordered search results to a user wherein documents having a higher level of activation are in a higher order position.

4. A system for providing a ranking for a set of documents representing search results from a collection of linked documents comprising:

means for generating historical information of the usage of said collection of linked documents;

means for defining said set of documents as initial activation information, said initial activation information indicating a set of focus documents for said collection of linked documents;

spreading activation means for performing a spreading activation operation based on said initial activation information and historical information based on a network representation of said collection of linked documents, said spreading operation performed to obtain activation information from said set of documents; and

means for ranking said set of documents based on said activation information for said set of documents.

5. The system as recited in claim 4 wherein said means for generating historical information regarding the usage of said collection of linked documents is further comprised of:

means for gathering usage data for 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; and

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.

6. The system as recited in claim 5 wherein said spreading activation means is further comprised of

activation means for causing simulated access of documents through said network representations of said collection of linked documents;

and

extraction means for extracting activation information resulting when a stable pattern of activation across all nodes of said network representation of said collection of linked documents is reached.

7. A system for submitting search requests to collections of linked documents and obtaining results ordered based on historical usage comprising:

a user interface for submitting search requests and viewing search results;

a search engine for processing search requests, said search engine coupled to a server for accessing said collection of linked documents;

an access prediction module coupled to said search engine to receive said search results, said access prediction module further coupled to obtain historical usage and topography data for said collection of linked documents, said access prediction module for generating activation information for said search results;

an ordering module coupled to said access prediction module, said search engine and said user interface, said ordering module for presenting an ordering of said search results based on said activation information.

8. The system as recited in claim 7 wherein said access prediction module is further comprised of:

circuitry for gathering historical usage and topology data for said collection of linked documents;

circuitry for generating an initial activation matrix from said search results;

circuitry for generating page to page transition information from said historical usage and topology data, said page to page transition information indicating a strength of association between documents in said collection of linked documents;

circuitry for generating link probability information from said historical usage and topology data, said link probability information indicating a distribution of the number of documents a user will access in said collection of linked documents; and

circuitry for performing a spreading activation operation using said initial activation matrix, page to page transition information and said link probability information to obtain activation information.

9. The system as recited in claim 8 wherein said ordering module is further comprised of circuitry for identifying activation information for each document in said search result and circuitry for presenting said search results in an order based on the activation information for each document in said search results.