Taxonomy generation for electronic documents

• US 7,243,092 B2
• Filed: 08/29/2002
• Issued: 07/10/2007
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Faerber, Franz, Woehler, Johannes
• Primary Examiner(s): Breene; John E.
• Assistant Examiner(s): To; Baoquoc N.
• Application Number:
  US10/233,019
• Publication Number:
  US 20030126561A1
• Time in Patent Office: 1,776 Days
• Field of Search: 707 1- 10, 707/104.1, 707200-205, 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Systems and techniques to generate a term taxonomy for a collection of documents and filling the taxonomy with documents from the collection. In general, in one implementation, the technique includes: extracting terms from a plurality of documents; generating term pairs from the terms; ranking terms in each term pair based on a relative specificity of the terms; aggregating the ranks of the terms in each term pair; selecting term pairs based on the aggregate rankings; and generating a term hierarchy from the selected term pairs.

Claims

1. A computer-implemented method comprising:

extracting terms from a plurality of electronic documents;

ranking the extracted terms using two or more term ranking algorithms;

aggregating rankings of the ranked extracted terms to produce first aggregate rankings, each of the rankings resulting from one of the two or more ranking algorithms;

selecting terms from the extracted terms, the selected terms having the first aggregate rankings above a pre-determined threshold;

generating term pairs from the selected terms;

ranking terms in each term pair based on a relative specificity of the selected terms using two more term pair ranking algorithms;

aggregating the ranks of the terms in each term pair to produce second aggregate rankings, each of the ranks resulting from the two or more term pair ranking algorithms;

selecting term pairs having the second aggregate rankings above a pre-determined threshold;

generating a term hierarchy from the selected term pairs;

assigning documents to nodes of the term hierarchy based on a number of terms within a branch of the term hierarchy associated with each node that match terms extracted from each document; and

storing assignments of the documents to the nodes to a memory for retrieval of one or more documents responsive to a search query.

2. The method of claim 1, wherein the extracted terms are ranked based on frequency.

3. The method of claim 1, wherein the two or more term ranking algorithms include a TFIDF (Text Frequency and Inverse Document Frequency) algorithm.

4. The method of claim 1, wherein the two or more term ranking algorithms include a corpus based extraction algorithm.

5. The method of claim 1, further comprising:

pre-selecting term pairs based on a similarity between the terms in each term pair.

6. The method of claim 5, further comprising:

generating a vector formed by frequencies of terms in the term pairs for the documents; and

determining a similarity between the terms in each term pair based on the vector.

7. The method of claim 1, wherein the two or more term pair ranking algorithms include a concept hierarchy algorithm.

8. The method of claim 1, wherein the two or more term pair ranking algorithms include a combination of a frequency-based method and a modifier method.

9. The method of claim 1, wherein the two or more term pair ranking algorithms include a sentence particle extraction algorithm.

10. The method of claim 1, wherein the two or more pair ranking algorithms include an algorithm that searches for compounded nouns.

11. The method of claim 1, further comprising optimizing the term hierarchy by removing one or more term pairs.

22. The method of claim 1, wherein the term pairs are generated from terms having similar rankings in the first aggregate rankings.

23. The method of claim 1, wherein the extracted terms are extracted regardless of a pre-existing taxonomy, the term hierarchy is generated without a provided taxonomy, and the extracting occurs before the generating the term hierarchy.

24. The method of claim 1, further comprising:

presenting to a user a list of results to a search, the list of results comprising documents assigned to terms in the term hierarchy matching criteria of the search.

25. The method of claim 1, further comprising:

presenting to a user the results to a search, the results comprising documents assigned to terms in the term hierarchy matching criteria of the search and the results being organized in a hierarchy in accordance with the term hierarchy.

12. An article comprising a machine-readable medium storing instructions executed by one or more machines to perform operations comprising:

extracting terms from a plurality of electronic documents;

ranking the extracted terms using two or more term ranking algorithms;

aggregating rankings of the ranked extracted terms to produce first aggregate rankings, each of the rankings resulting from one of the two or more ranking algorithms;

selecting terms from the extracted terms, the selected terms having the first aggregate rankings above a pre-determined threshold;

generating term pairs from the selected terms;

ranking terms in each term pair based on a relative specificity of the selected terms using two more term pair ranking algorithms;

aggregating the ranks of the terms in each term pair to produce second aggregate rankings, each of the ranks resulting from the two or more term pair ranking algorithms;

selecting term having the second aggregate rankings above a pre-determined threshold;

generating a term hierarchy from the selected term pairs; and

storing assignments of the documents to the nodes to a memory for retrieval of one or more documents responsive to a search query.

13. The article of claim 12, wherein the extracted terms are ranked based on frequency.

14. The article of claim 12, wherein the two or more term ranking algorithms include at least one of a TFIDF (Text Frequency and Inverse Document Frequency) algorithm and a corpus based extraction algorithm.

15. The article of claim 12, wherein the operations further comprise:

pre-selecting term pairs based on a similarity between the terms in each term pair.

16. The article of claim 12, wherein the operations further comprise:

generating a vector formed by frequencies of terms in the term pairs for the documents; and

determining a similarity between the terms in each term pair based on the vector.

17. The article of claim 12, wherein the two or more term pair ranking algorithms are chosen from a group comprising:

concept hierarchy algorithms, algorithms including a combination of a frequency-based method and a modifier method, sentence particle extraction algorithms, and algorithms that search for compounded nouns.

18. The article of claim 12, wherein the operations further comprise:

optimizing the term hierarchy by removing one or more term pairs.

19. The article of claim 12, wherein the operations further comprise:

assigning documents to nodes of the term hierarchy based on a number of teens within a branch of the term hierarchy associated with each node that match terms extracted from each document.

20. An apparatus comprising:

a processor executing instructions to perform operations comprising;

ranking extracted terms using two or more term ranking algorithms, the extracted terms extracted from a plurality of electronic documents;

aggregating rankings of the ranked extracted terms to produce first aggregate rankings, each of the rankings resulting from one of the two or more ranking algorithms;

selecting terms from the extracted terms, the selected terms having the first aggregate rankings above a pre-determined threshold;

generating term pairs from the selected terms;

ranking terms in each term pair based on a relative specificity of the selected terms using two more term pair ranking algorithms;

aggregating the ranks of the terms in each term pair to produce second aggregate rankings, each of the ranks resulting from the two or more term pair ranking algorithms;

selecting term pairs having the second aggregate rankings above a pre-determined threshold;

generating a term hierarchy from the selected term pairs; and

storing the term hierarchy to a memory for retrieval of one or more documents responsive to a search query.

21. The apparatus of claim 20, wherein the processor further performs operations comprising:

assigning documents to nodes of the term hierarchy based on a number of terms within a branch of the term hierarchy associated with each node tat match terms extracted from each document.