Automatically generating a hierarchy of terms

• US 8,332,439 B2
• Filed: 10/01/2008
• Issued: 12/11/2012
• Est. Priority Date: 10/05/2007
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Marvit, David L., Jain, Jawahar, Stergiou, Stergios, Gilman, Alex, Adler, B. Thomas
• Primary Examiner(s): LU, KUEN S
• Application Number:
  US12/242,965
• Publication Number:
  US 20090094208A1
• Time in Patent Office: 1,532 Days
• Field of Search: 707/803, 707/778
• US Class Current: 707/803
• 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
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

In certain embodiments, generating a hierarchy of terms includes accessing a corpus comprising terms. The following is performed for one or more terms to yield parent-child relationships: one or more parent terms of a term are identified according to directional affinity; and one or more parent-child relationships are established from the parent terms and each term. A hierarchical graph is automatically generated from the parent-child relationships.

Claims

1. A method comprising:

accessing a corpus stored in one or more tangible media, the corpus comprising a plurality of terms;

performing the following for each term of one or more terms of the plurality of terms to yield a plurality of parent-child relationships;

identifying one or more parent terms of the each term according to directional affinity, the plurality of terms comprising the one or more parent terms,

the directional affinity being the number of co-occurrence contexts that include two terms, over the number of co-occurrence contexts that include one term; and

establishing one or more parent-child relationships from the one or more parent terms and the each term; and

automatically generating a hierarchical graph from the plurality of parent-child relationships,

wherein the automatically generating the hierarchical graph from the plurality of parent-child relationships comprises reducing the hierarchical graph by;

identifying a parent-child relationship and a redundant parent-child relationship of the hierarchical graph; and

removing the redundant parent-child relationship from the hierarchical graph.

2. The method of claim 1, the identifying the one or more parent terms of the each term according to directional affinity further comprising:

determining that there is a high directional affinity from the each term to a candidate parent term;

determining that there is a low non-zero directional affinity from the candidate parent term to the each term; and

identifying the candidate parent term as a parent term of the each term.

3. The method of claim 1, the identifying the one or more parent terms of the each term according to directional affinity further comprising:

determining that a directional affinity from the each term to a candidate parent term is greater than 0.6 and less than or equal to one;

determining that a directional affinity from the candidate parent term to the each term is less than 0.4 and greater than 0.1; and

identifying the candidate parent term as a parent term of the each term.

4. The method of claim 1:

the corpus comprising a plurality of documents, the plurality of documents comprising the plurality of terms; and

the hierarchical graph representing a catalog of the plurality of documents.

5. The method of claim 1:

the corpus comprising a plurality of search results;

a term of the one or more terms representing a topic of a search result; and

the hierarchical graph describing the plurality of parent-child relationships of the plurality of search results.

6. The method of claim 1:

the corpus comprising a plurality of search results organized into a plurality of clusters;

a term of the one or more terms representing a topic of a cluster; and

the hierarchical graph describing the plurality of parent-child relationships of the plurality of search results.

7. The method of claim 1, further comprising:

sending a plurality of parent terms of the hierarchical graph to a client;

receiving a selection of a parent term, the selected parent term having a plurality of child terms; and

sending the plurality of child terms to the client.

8. The method of claim 1, further comprising:

receiving a search query comprising a parent term of the hierarchical graph;

identifying one or more child terms of the parent term; and

searching the corpus using the parent term and the one or more child terms.

9. The method of claim 1:

the corpus comprising a plurality of documents, the plurality of documents comprising the plurality of terms; and

further comprising;

associating each graph term of the hierarchical graph with a document that includes the each graph term;

receiving a search query comprising a parent term; and

retrieving one or more documents associated with a child of the parent term.

10. One or more non-transitory computer-readable tangible media encoding software operable when executed to:

access a corpus stored in one or more tangible media, the corpus comprising a plurality of terms;

perform the following for each term of one or more terms of the plurality of terms to yield a plurality of parent-child relationships;

identify one or more parent terms of the each term according to directional affinity, the plurality of terms comprising the one or more parent terms,

the directional affinity being the number of co-occurrence contexts that include two terms, over the number of co-occurrence contexts that include one term; and

establish one or more parent-child relationships from the one or more parent terms and the each term; and

automatically generate a hierarchical graph from the plurality of parent-child relationships,

wherein the automatically generating the hierarchical graph from the plurality of parent-child relationships comprises reducing the hierarchical graph by;

identifying a parent-child relationship and a redundant parent-child relationship of the hierarchical graph; and

removing the redundant parent-child relationship from the hierarchical graph.

11. The computer-readable tangible media of claim 10, the software further operable to identify the one or more parent terms of the each term according to directional affinity by:

determining that there is a high directional affinity from the each term to a candidate parent term;

determining that there is a low directional affinity from the candidate parent term to the each term;

determining that a directional affinity from the candidate parent term to the each term is above a minimum threshold; and

identifying the candidate parent term as a parent term of the each term.

12. The computer-readable tangible media of claim 10, the software further operable to identify the one or more parent terms of the each term according to directional affinity by:

determining that a directional affinity from the each term to a candidate parent term is greater than 0.6 and less than or equal to one;

determining that a directional affinity from the candidate parent term to the each term is less than 0.4 and greater than 0.1; and

identifying the candidate parent term as a parent term of the each term.

13. The computer-readable tangible media of claim 10:

the corpus comprising a plurality of documents, the plurality of documents comprising the plurality of terms; and

the hierarchical graph representing a catalog of the plurality of documents.

14. The computer-readable tangible media of claim 10:

the corpus comprising a plurality of search results;

a term of the one or more terms representing a topic of a search result; and

the hierarchical graph describing the plurality of parent-child relationships of the plurality of search results.

15. The computer-readable tangible media of claim 10:

the corpus comprising a plurality of search results organized into a plurality of clusters;

a term of the one or more terms representing a topic of a cluster; and

the hierarchical graph describing the plurality of parent-child relationships of the plurality of search results.

16. The computer-readable tangible media of claim 10, the software further operable to:

send a plurality of parent terms of the hierarchical graph to a client;

receive a selection of a parent term, the selected parent term having a plurality of child terms; and

send the plurality of child terms to the client.

17. The computer-readable tangible media of claim 10, the software further operable to:

receive a search query comprising a parent term of the hierarchical graph;

identify one or more child terms of the parent term; and

search the corpus using the parent term and the one or more child terms.

18. The computer-readable tangible media of claim 10:

the corpus comprising a plurality of documents, the plurality of documents comprising the plurality of terms; and

the software further operable to;

associate each graph term of the hierarchical graph with a document that includes the each graph term;

receive a search query comprising a parent term; and

retrieve one or more documents associated with a child of the parent term.