Methods and systems for automated semantic knowledge leveraging graph theoretic analysis and the inherent structure of communication

• US 7,571,177 B2
• Filed: 02/08/2002
• Issued: 08/04/2009
• Est. Priority Date: 02/08/2001
• Status: Active Grant

• Current Assignee: 2028 Incorporated
• Original Assignee: 2028 Incorporated
• Inventors: Damle, Aditya
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): COLAN, GIOVANNA B
• Application Number:
  US10/467,251
• Publication Number:
  US 20040093328A1
• Time in Patent Office: 2,734 Days
• Field of Search: 707/100, 707/3, 707/5, 707/501.1, 707101-103 R, 715/501.1, 706/55
• US Class Current: 1/1
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/367 Ontology
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A system that processes a collection of one or more documents and thereby constructs a knowledge base is described. The system leverages innovative graph theoretical analysis of documents leveraging the inherent structure in communication. Through the generation of the automated knowledge base the system is able to provides intra-document analysis such as variable summarization and indexing, document key concepts, better filtering and relevance matching on a semantic level for documents, context dependant directories, document categorization, better basis for natural language processing, new knowledge and information through the amalgamation of the data (collection intelligence).

Claims

1. A system having a memory for generating a document summary, the system comprising:

receiving means for receiving a set of documents, the documents comprising a collection of related symbols wherein document structure specifies relationships between and among the symbols;

graph generating means, in communication with the receiving means, for generating, based on the received set of documents, conceptual graphs indicative of relevance of concepts or sub-concepts within one or more documents in the set of documents, the graph generating means comprising

a semantic relevance filter for testing groups of concepts or sub-concepts as possible conceptual centers of semantic relevance and determining which concepts are semantically central and which are peripheral, thereby generating semantic relevance relationship vectors that define the relative semantic relevance between and among concepts in each document, wherein the semantic relevance filter utilizes information structure inherent in the documents in testing groups of concepts or sub-concepts, the information structure including any of symbol position, symbol co-proximity, highlighted symbols, or consecutive groupings of symbols, and wherein the testing process is iterated for each term, where the semantic relevance filter further comprises noise reduction means for removing noise from a document by analyzing the structure of the document, the noise reduction means including;

means for determining the grouping of concepts in the document;

means for determining a hierarchy among the concepts;

means for determining how information is distributed through the hierarchy; and

means for determining, based on the determined information distribution, what portion of the document is attempting to convey information;

and normalizing means, in communication with the testing means, for normalizing semantic relevance scores assigned to each concept, across the total number of concepts;

determining means, in communication with the graph generating means, for determining from the conceptual graphs a set of directed conceptual relation vectors, utilizing a selected heuristic, the heuristic including utilizing a derived semantic ordering to determine a direction of each vector, from general to specific; and

summary generating means, in communication with the determining means, for creating, based on the vectors, a summary of at least one document in the set of received documents, the summary being generated from sentences or sentence fragments in the document, the summary generating means including ranking means for ranking sentences or sentence fragments in accordance with any of core ideas contained therein or relationships expressed there between.

2. The system of claim 1 wherein the summary generating means can generate summaries of selected length.

3. The system of claim 2 wherein smaller summaries generated by the summary generating means are conceptually more compact than longer summaries.

4. The system of claim 1 wherein the summary generating means can generate summaries that favor or disfavor selected concepts or conceptual relationships.

5. The system of claim 1 wherein the noise reducing means utilizes information generated by the semantic relevance filter, representative of semantically relevant concepts and their distribution through the hierarchy of concepts in the document.

6. The system of claim 1 wherein the semantic relevance filter further includes means for utilizing available topological information to determine the semantic relevance of a concept of a given document or the semantic relationships between concepts.

7. The system of claim 6 wherein the means for utilizing topological information includes means for analyzing topological information in the form of a tree taxonomy including parent and child nodes.

8. The system of claim 7 wherein the topological information is available from any of a website hierarchy, a document hierarchy, or a file system hierarchy.

9. The system of claim 7 further comprising:

inverted filter means for utilizing the semantic relevance of a concept in a child node to modify the semantic relevance of a concept in a parent node.

10. The system of claim 1 further comprising means for generating conceptual maps of a collection of documents or subsets thereof.

11. The system of claim 1 further comprising means for creating new information structures from collections of documents.

12. The system of claim 11 further comprising means for collecting information from the Internet based on a user-specified universe of concepts.

13. The system of claim 11 wherein the system further comprises means for organizing collections of documents in accordance with user-specified parameters.

14. The system of claim 13 wherein the collections of documents are on a local processor.

15. The system of claim 13 wherein the collections of documents are on a remote processor.

16. The system of claim 11 further comprising means for generating an adaptive index of a collection of documents.

17. The system of claim 16 wherein the collection of documents is on a local processor.

18. The system of claim 16 wherein the collection of documents is on a remote processor.

19. The system of claim 1 further comprising means for collecting and organizing information from message boards.

20. The system of claim 1 further comprising means for filtering unwanted information from access by a user.

21. The system of claim 1 further comprising means for optimizing Web caching in accordance with conceptual semantic relevance.

22. The system of claim 1 further comprising means for optimizing analysis of information flow in accordance with conceptual semantic relevance.