Automatically Generating A Hierarchy Of Terms

• US 20090094208A1
• Filed: 10/01/2008
• Published: 04/09/2009
• Est. Priority Date: 10/05/2007
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Adler, B. Thomas, Gilman, Alex, Marvit, David L., Stergiou, Stergios, Jain, Jawahar
• Granted Patent: US 8,332,439 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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; 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.

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;

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 automatically generating the hierarchical graph from the plurality of parent-child relationships further comprising 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. One or more 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; 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.

12. The computer-readable tangible media of claim 11, 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.

13. The computer-readable tangible media of claim 11, 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;

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.

14. The computer-readable tangible media of claim 11, the software further operable to automatically generate the hierarchical graph from the plurality of parent-child relationships by 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.

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

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.

16. The computer-readable tangible media of claim 11:

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.

17. The computer-readable tangible media of claim 11:

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.

18. The computer-readable tangible media of claim 11, 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.

19. The computer-readable tangible media of claim 11, 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.

20. The computer-readable tangible media of claim 11:

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.

21. A system comprising:

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

means for 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; and

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

means for automatically generating a hierarchical graph from the plurality of parent-child relationships.