System and method for generating a taxonomy from a plurality of documents

• US 6,665,681 B1
• Filed: 04/09/1999
• Issued: 12/16/2003
• Est. Priority Date: 04/09/1999
• Status: Expired due to Term

• Current Assignee: Amobee, Inc. (Nexxen International Ltd.)
• Original Assignee: Entrieva, Inc. (Nexxen International Ltd.)
• Inventors: Vogel, Claude
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/289,174
• Time in Patent Office: 1,712 Days
• Field of Search: 702/101, 707/3, 707/102, 707/501, 707/4, 707/5, 704/1
• US Class Current: 707/738
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/367 Ontology
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and method for generating a taxonomy is provided in which the taxonomy is generated based on clusters of phrases and a topical library. The taxonomy permits a user of a text processing system to rapidly search through a database and find relevant documents since the classifications in the taxonomy are narrow enough to limit the number of documents classified in each classifications.

Claims

1. A system for generating a taxonomy for a database, the system comprising:

a database including a plurality of pieces of text and a plurality of phrases extracted from the pieces of text;

means for clustering the phrases extracted from the plurality of pieces of text in order to determine associations between the extracted phrases in the same piece of text and across the plurality of pieces of text;

means for identifying a leader phrase from the clustered phrases in the database, the leader phrase being associated with a predetermined number of other phrases in the database;

means for generating a first level of taxonomy based on the identified leader phrases, the leader phrases forming a first level of headings in a hierarchical topical outline; and

means for generating a second level of the taxonomy based on phrases in the database associated with the leader phrases, the phrases being sub-headings underneath the leader phrases with which they are associated, the taxonomy reflecting the phrases extracted from the pieces of text in the database so that a user searches through the database using the final taxonomy.

2. The system of claim 1 further comprising means for combining the taxonomy with a topical library to form a final taxonomy so that the final taxonomy reflects the phrases extracted from the pieces of text in the database so that a user searches through the database using the final taxonomy.

3. The system of claim 1, wherein the means for generating the first and second levels of the taxonomy comprise means for parsing a set of one or more text documents to extract one or more phrases from each document, means for clusterizing for processing the one or more phrases from the documents to generate associations between the extracted phrases, and means for generating a taxonomy that generates a unique final taxonomy for the set of documents based on the extracted phrases and the associations between the extracted phrases.

4. The system of claim 1, wherein the system comprises one or more software application.

5. The system of claim 1 further comprising means for populating the final taxonomy wherein the one or more pieces of text from the database are attached to first and second levels of the taxonomy.

6. A method for generating a taxonomy for a database, the method comprising:

processing a plurality of pieces of text and a plurality of phrases extracted from the pieces of text stored in a database;

means for clustering the phrases extracted from the plurality of pieces of text in order to determine associations between the extracted phrases in the same piece of text and across the plurality of pieces of text;

identifying a leader phrase from the clustered phrases in the database, the leader phrase being associated with a predetermined number of other phrases in the database;

generating a first level of a taxonomy based on the identified leader phrases, the leader phrases forming a first level of headings in a hierarchical topical outline; and

generating a second level of the taxonomy based on phrases in the database associated with the leader phrases, the phrases being sub-headings underneath the leader phrases with which they are associated, the taxonomy reflecting the phrases extracted from the pieces of text in the database so that a user searches through the database using the final taxonomy.

7. The method of claim 6 further comprising combining the taxonomy with a topical library to form a final taxonomy so that the final taxonomy reflects the phrases extracted from the pieces of text in the database so that a user searches through the database using the final taxonomy.

8. The method of claim 6, wherein generating the first and second levels of the taxonomy comprise parsing a set of one or more text documents to extract one or more phrases from each document, clusterizing for processing the one or more phrases from the documents to generate associations between the extracted phrases, and generating a taxonomy that generates a unique final taxonomy for the set of documents based on the extracted phrases and the associations between the extracted phrases.

9. The method of claim 6 further comprising populating the final taxonomy wherein the one or more pieces of text from the database are attached to first and second levels of the taxonomy.

10. A taxonomy generating system, comprising:

a parser that processes a set of one or more text documents to extract one or more phrases from each document;

a clusterizer that processes the one or more phrases from the documents to generate associations between the extracted phrases in the same piece of text and across the plurality of pieces of text;

a map generator that generates a map of the associations between the extracted phases;

a taxonomy generator that generates a unique final taxonomy for the set of documents based on the clustered extracted phrases and the associations between the extracted phrases in the map; and

a database for storing a topical index containing one or more broad classifications of topics, wherein the taxonomy generator further comprises a leader phrase identifier that identifies a leader phrase from the extracted phrases, the leader phrase being associated with a predetermined number of other phrases, an organizer that generates a first level of a taxonomy based on the identified leader phrases in which the leader phrases form a first level of headings in a hierarchical topical outline and that generates a second level of the taxonomy based on extracted phrases associated with the leader phrases, the phrases being sub-headings underneath the leader phrases with which they are associated and a combiner for combining the first and second levels of the taxonomy with the topical index to form the taxonomy unique to the set of documents.

11. The system of claim 10, further comprising means for populating the final taxonomy wherein the one or more pieces of text from the database are attached to first and second levels of the taxonomy.