Process and system for mapping the relationship of the content of a collection of documents

• US 5,808,615 A
• Filed: 05/01/1996
• Issued: 09/15/1998
• Est. Priority Date: 05/01/1996
• Status: Expired due to Term

• Current Assignee: Ent Services Development Corporation LP (DXC Technology Company)
• Original Assignee: Electronic Data Systems Corporation (Perspecta, Inc.)
• Inventors: Thompson, Gregory J., Hill, Joe R.
• Primary Examiner(s): KATBAB, ABDOLLAH
• Application Number:
  US08/640,604
• Time in Patent Office: 867 Days
• Field of Search: 395/356, 395/603, 395/140, 395/968, 345/356, 345/357, 345/603, 345/613, 345/968, 345/969, 345/774, 345/776, 345/440, 707/102, 707/513, 707/514
• US Class Current: 715/853
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence

Abstract

A process is provided for mapping the relationship of the content of a collection of documents (14). The process includes providing a collection (12) of documents (14) where each document (14) includes text. Relevance measures are determined that represent a relevance between each pair of documents (14) based upon the text of the documents (14). A graph (22) is then generated that has nodes (30) and edges (32) with each edge (32) connecting two nodes (30). The graph (22) has a node (30) associated with each document (14) and has an edge (32) connecting nodes (30) for which the relevance measure between associated documents (14) is greater than a specified threshold. In this manner, the graph (22) maps the relationship of the content of the collection (12) of documents (14).

Claims

1. An automated process, using a computer, for mapping a relationship of content of a collection of documents, comprising:

providing a collection of documents, each document including content;

determining relevance measures, each relevance measure representing a relevance between a pair of documents, each relevance measure comprising a log likelihood ratio relevance measure, and each relevance measure based upon a comparison of the content of the pair of documents; and

generating a content graph having nodes and edges, each edge connecting two nodes, the content graph having a node associated with each document and having an edge connecting nodes for which the relevance measure between associated documents is greater than a specified threshold;

such that the content graph maps the relationship of the content of the collection of documents.

2. The process of claim 1, wherein generating the content graph comprises:

creating a node associated with each document;

selecting a pair of nodes to process;

determining whether the relevance measure between the selected pair of nodes is greater than a specified threshold;

if so, connecting the selected pair of nodes with an edge and associating the relevance measure with the edge; and

repeating selecting, determining and connecting until there are no unprocessed pairs of nodes.

3. The process of claim 2, wherein generating a content graph further includes generating a directed graph by determining a direction of the edge between each selected pair of nodes based upon specified criteria.

4. The process of claim 1, wherein each document includes text that describes the content and each relevance measure is based upon a comparison of the text of each pair of documents.

5. The process of claim 1, further comprising generating a layout based upon the content graph to provide a visual display of the relationship between the documents.

6. The process of claim 5, wherein generating a layout comprises generating a time-based layout.

7. The process of claim 5, wherein generating a layout comprises generating a gravity layout.

8. The process of claim 5, wherein generating a layout comprises generating a minimum-energy layout.

9. An automated system for mapping a relationship of content of a collection of documents, comprising:

a data storage device storing relevance measures, each relevance measure representing a relevance between a pair of documents in a collection of documents, each relevance measure comprising a log likelihood ratio relevance measure, and each relevance measure based upon a comparison of the content of the pair of documents;

a memory device operable to store a software program; and

a processor coupled to the data storage device and the memory device, the processor operable to execute the software program to;

generate a content graph having nodes and edges, each edge connecting two nodes, the content graph having a node associated with each document and having an edge connecting nodes for which the relevance measure between associated documents is greater than a specified threshold;

such that the content graph maps the relationship of the content of the collection of documents.

10. The system of claim 9, wherein generating the content graph comprises:

creating a node associated with each document;

selecting a pair of nodes to process;

determining whether the relevance measure between the selected pair of nodes is greater than a specified threshold;

if so, connecting the selected pair of nodes with an edge and associating the relevance measure with the edge; and

repeating selecting, determining and connecting until there are no unprocessed pairs of nodes.

11. The system of claim 10, wherein the content graph is a directed content graph generated by determining a direction of the edge between each selected pair of nodes based upon specified criteria.

12. The system of claim 9, wherein each document includes text that describes the content and each relevance measure is based upon a comparison of the text of each pair of documents.

13. The system of claim 9, wherein the processor is further operable to execute the software program to generate a layout based upon the content graph to provide a visual display of the relationship between the documents.

14. The system of claim 13, wherein the layout comprises a time-based layout.

15. The system of claim 13, wherein the layout comprises a gravity layout.

16. The system of claim 13, wherein the layout comprises a minimum-energy layout.

17. An automated system for mapping a relationship of content of a collection of documents, comprising:

a collection of documents, each document including content;

a relevance generator connected to access the collection of documents, the relevance generator operable to generate relevance measures, each relevance measure representing a relevance between a pair of documents, each relevance measure comprising a log likelihood ratio relevance measure, and each relevance measure based upon a comparison of the content of the pair of documents;

a graph generator connected to access the relevance measures, the graph generator operable to generate a content graph having nodes and edges where each edge connects two nodes, the content graph having a node associated with each document and having an edge connecting nodes for which the relevance measure between associated documents is greater than a specified threshold; and

a layout generator connected to access the content graph, the layout generator operable to generate a layout based upon the content graph to provide a visual display of the relationship between the documents.

18. The system of claim 17, wherein each document includes text that describes the content and each relevance measure is based upon a comparison of the text of each pair of documents.

19. The system of claim 17, wherein graph generator generates the content graph by:

creating a node associated with each document;

selecting a pair of nodes to process;

determining whether the relevance measure between the selected pair of nodes is greater than a specified threshold;

if so, connecting the selected pair of nodes with an edge and associating the relevance measure with the edge; and

repeating selecting, determining and connecting until there are no unprocessed pairs of nodes.

20. The system of claim 19, wherein the content graph is a directed content graph generated by determining a direction of the edge between each selected pair of nodes based upon specified criteria.