Determining Words Related To A Given Set Of Words

• US 20090204609A1
• Filed: 02/10/2009
• Published: 08/13/2009
• Est. Priority Date: 02/13/2008
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Adler, B. Thomas, Labrou, Yannis, Marvit, David L., Stergiou, Stergios, Reinhardt, Albert
• Granted Patent: US 8,280,886 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence

Abstract

In one embodiment, display of a user entry window of a graphical user interface is initiated. Search terms entered into the user entry window to initiate a first search are received. One or more first search results from a corpus of documents are determined according to the search terms. Display of the search terms at a current search terms window of the graphical user interface is initiated. Display of the first search results at a search results window of the graphical user interface is initiated. Display of the first search suggestions at a search suggestion window of the graphical user interface is initiated.

Claims

1. An apparatus comprising:

an interface configured to receive an initial set of terms of a query; and

a processor configured to perform a method comprising;

initializing a set of candidate terms;

performing the following for a predetermined number of iterations;

obtaining a predetermined number of temporary terms for each candidate term of the set of candidate terms, the predetermined number of temporary terms having a higher differential affinity to the each candidate term;

placing each temporary term and the associated higher differential affinity into a set of temporary terms, if a temporary term is obtained from more than one candidate term, the differential affinity of the temporary term being related to the differential affinities to the more than one candidate term;

calculating an average differential affinity for each temporary term of the set of temporary terms, the average differential affinity representing an average of differential affinities from the each temporary term to every term of the initial set of terms;

removing from the temporary set one or more terms with an average differential affinity that fails to satisfy a predetermined threshold; and

placing one or more terms of the temporary set with higher differential affinities into the set of candidate terms;

selecting one or more terms of the set of candidate terms; and

returning the one or more selected terms.

2. The apparatus of claim 1, the processor configured to select the one or more terms of the set of candidate terms by:

determining an average affinity of each term of the set of candidate terms; and

selecting the one or more terms with higher average affinities.

3. The apparatus of claim 1, the processor configured to select the one or more terms of the set of candidate terms by:

determining a second average differential affinity for each term of the one or more terms, the second average differential affinity representing an average of differential affinities from the each term to every term of the set of candidate terms; and

selecting the one or more terms with higher second average differential affinities.

4. The apparatus of claim 1, the processor configured to initialize the set of candidate terms by:

initializing the set of candidate terms to comprise the initial set of terms.

5. The apparatus of claim 1, the processor configured to:

receive a weighted directional graph comprising a plurality of nodes and a plurality of directed edges with weights, a node corresponding to a term, the weight of a directed edge corresponding to the directional affinity from a first term to a second term, an average of weights of incoming edges to a node corresponding to the average affinity of the node; and

perform the method on the weighted directional graph.

6. The apparatus of claim 1, comprising a search engine configured to perform the method.

7. An method comprising:

receiving an initial set of terms of a query;

initializing a set of candidate terms;

performing the following for a predetermined number of iterations;

obtaining a predetermined number of temporary terms for each candidate term of the set of candidate terms, the predetermined number of temporary terms having a higher differential affinity to the each candidate term;

placing each temporary term and the associated higher differential affinity into a set of temporary terms, if a temporary term is obtained from more than one candidate term, the differential affinity of the temporary term being related to the differential affinities to the more than one candidate term;

calculating an average differential affinity for each temporary term of the set of temporary terms, the average differential affinity representing an average of differential affinities from the each temporary term to every term of the initial set of terms;

removing from the temporary set one or more terms with an average differential affinity that fails to satisfy a predetermined threshold; and

placing one or more terms of the temporary set with higher differential affinities into the set of candidate terms;

selecting one or more terms of the set of candidate terms; and

returning the one or more selected terms.

8. The method of claim 7, the selecting the one or more terms of the set of candidate terms further comprising:

determining an average affinity of each term of the set of candidate terms; and

selecting the one or more terms with higher average affinities.

9. The method of claim 7, the selecting the one or more terms of the set of candidate terms further comprising:

determining a second average differential affinity for each term of the one or more terms, the second average differential affinity representing an average of differential affinities from the each term to every term of the set of candidate terms; and

selecting the one or more terms with higher second average differential affinities.

10. The method of claim 7, the initializing the set of candidate terms further comprising:

initializing the set of candidate terms to comprise the initial set of terms.

11. The method of claim 7, further comprising:

receiving a weighted directional graph comprising a plurality of nodes and a plurality of directed edges with weights, a node corresponding to a term, the weight of a directed edge corresponding to the directional affinity from a first term to a second term, an average of weights of incoming edges to a node corresponding to the average affinity of the node; and

performing the method on the weighted directional graph.

12. The method of claim 7, performed by a search engine.

13. An apparatus comprising:

a tangible computer readable medium configured to store a set of terms; and

a processor configured to;

determine a term frequency-inverse document frequency (TF-IDF) value for each term of the set of terms of a document;

sort the terms according to the TF-IDF values to yield a sorted list, a first term with the highest TF-IDF value being at the top of the sorted list, a second term with the lowest TF-IDF value being at the bottom of the sorted list;

calculate a difference in TF-IDF values of successive terms for each of the successive terms of the sorted list to yield a plurality of differences;

calculate a standard deviation of the differences;

remove one or more terms from the sorted list according to the standard deviation; and

output the remaining terms.

14. The apparatus of claim 13, the processor configured to:

remove terms below a percentile threshold from the sorted list.

15. The apparatus of claim 13, the processor configured to remove the one or more terms from the sorted list according to the standard deviation by determining a next TF-IDF threshold by repeating the following one or more times:

scanning the sorted list from the bottom towards the top until a difference in TF-IDF values greater than a standard deviation threshold is encountered, the difference being between a higher TF-IDF value and a lower TF-IDF value;

designating the higher TF-IDF value as the next TF-IDF threshold; and

removing from the sorted list one or more terms having a TF-IDF value that fails to satisfy the next TF-IDF threshold.

16. The apparatus of claim 13, the processor configured to:

remove from the sorted list one or more terms having a TF-IDF value that fails to satisfy a TF-IDF threshold while maintaining a required minimum number of terms in the sorted list.

17. The apparatus of claim 13, the processor configured to:

remove one or more infrequently occurring terms from the set of terms.

18. The apparatus of claim 17, the one or more infrequently occurring terms comprising one or more terms that occur less than a predetermined number of times in a document.

19. The apparatus of claim 17, the one or more infrequently occurring terms are identified using a frequency distribution of terms across a corpus.

20. The apparatus of claim 13, the processor configured to determine a term frequency-inverse document frequency (TF-IDF) value for each term of the set of terms by:

calculating the TF-IDF value according to a corpus comprising a plurality of documents.

21. A method comprising:

determining a term frequency-inverse document frequency (TF-IDF) value for each term of a set of terms of a document;

sorting the terms according to the TF-IDF values to yield a sorted list, a first term with the highest TF-IDF value being at the top of the sorted list, a second term with the lowest TF-IDF value being at the bottom of the sorted list;

calculating a difference in TF-IDF values of successive terms for each of the successive terms of the sorted list to yield a plurality of differences;

calculating a standard deviation of the differences;

removing one or more terms from the sorted list according to the standard deviation; and

outputting the remaining terms.

22. The method of claim 21, further comprising:

removing terms below a percentile threshold from the sorted list.

23. The method of claim 21, the removing the one or more terms from the sorted list according to the standard deviation further comprising determining a next TF-IDF threshold by repeating the following one or more times:

scanning the sorted list from the bottom towards the top until a difference in TF-IDF values greater than a standard deviation threshold is encountered, the difference being between a higher TF-IDF value and a lower TF-IDF value;

designating the higher TF-IDF value as the next TF-IDF threshold; and

removing from the sorted list one or more terms having a TF-IDF value that fails to satisfy the next TF-IDF threshold.

24. The method of claim 21, further comprising:

removing from the sorted list one or more terms having a TF-IDF value that fails to satisfy a TF-IDF threshold while maintaining a required minimum number of terms in the sorted list.

25. The method of claim 21, further comprising:

removing one or more infrequently occurring terms from the set of terms.

26. The method of claim 25, the one or more infrequently occurring terms comprising one or more terms that occur less than a predetermined number of times in a document.

27. The method of claim 25, the one or more infrequently occurring terms are identified using a frequency distribution of terms across a corpus.

28. The method of claim 21, further comprising determining a term frequency-inverse document frequency (TF-IDF) value for each term of the set of terms by:

calculating the TF-IDF value according to a corpus comprising a plurality of documents.

29. An apparatus comprising:

a tangible computer readable medium configured to store a corpus of documents; and

a processor configured to;

initiate display of a user entry window of a graphical user interface;

receive a plurality of search terms entered into the user entry window to initiate a first search;

determine one or more first search results from the corpus according to the search terms;

initiate display of the search terms at a current search terms window of the graphical user interface;

initiate display of the one or more first search results at a search results window of the graphical user interface; and

initiate display of the one or more first search suggestions at a search suggestion window of the graphical user interface.

30. The apparatus of claim 29, the processor further configured to:

receive a selection of a search term to remove the search term, the selection made by clicking on the search term; and

remove the selected search term from the plurality of search terms for a second search.

31. The apparatus of claim 29, the processor further configured to:

receive a selection of a search suggestion to add the search suggestion, the selection made by clicking on the search suggestion; and

add the selected search suggestion to the plurality of search terms for a third search.

32. The apparatus of claim 29, the processor further configured to:

receive a selection of a search result, the selection made by clicking on the search result;

return one or more search results similar to the selected search result;

identify one or more additional search terms related to the selected search result;

add the one or more additional search terms to the search terms of the first search to initiate a next search; and

return one or more search results of the next search, the search results similar to the selected search result

33. The apparatus of claim 29, the processor further configured to:

receive a selection of a search result;

identify a plurality of terms related to the selected search result and that belong to an associated domain dictionary;

sort the terms by average affinity;

select a predetermined number of terms with higher average affinity; and

add the selected terms to the search terms of the first search to initiate a next search.

34. The apparatus of claim 29, the processor further configured to:

receive a selection of a search result;

identify a plurality of terms related to the selected search result and that are current search suggestions;

sort the terms by average affinity;

select a predetermined number of terms with higher average affinity; and

add the selected terms to the search terms of the first search to initiate a next search.

35. The apparatus of claim 29, the processor further configured to:

receive a selection of a search result to initiate a tagging mode, the selection made by clicking on the search result; and

enter a tagging mode.

36. The apparatus of claim 29, the processor further configured to:

generate a plurality of suggested tags for a search result;

initiate display of the suggested tags at the search suggestions window;

receive a selection of a suggested tag, the selection made by clicking on the suggested tag; and

tag the search result with the selected tag.

37. The apparatus of claim 29, the processor further configured to:

receive a selection of a suggested tag, the selection made by clicking on the suggested tag; and

add the suggested tag to the search terms to initiate a next search.

38. The apparatus of claim 29, the processor further configured to:

receive a selection of a search result, the selection made by clicking on the search result;

add the selected search result to the search terms to initiate a next search; and

return one or more search results of the next search.

39. The apparatus of claim 29, a search result comprising an image or video.

40. A method comprising:

initiating display of a user entry window of a graphical user interface;

receiving a plurality of search terms entered into the user entry window to initiate a first search;

determining one or more first search results from a corpus of documents according to the search terms;

initiating display of the search terms at a current search terms window of the graphical user interface;

initiating display of the one or more first search results at a search results window of the graphical user interface; and

initiating display of the one or more first search suggestions at a search suggestion window of the graphical user interface.

41. The method of claim 40, further comprising:

receiving a selection of a search term to remove the search term, the selection made by clicking on the search term; and

removing the selected search term from the plurality of search terms for a second search.

42. The method of claim 40, further comprising:

receiving a selection of a search suggestion to add the search suggestion, the selection made by clicking on the search suggestion; and

adding the selected search suggestion to the plurality of search terms for a third search.

43. The method of claim 40, further comprising:

receiving a selection of a search result, the selection made by clicking on the search result;

returning one or more search results similar to the selected search result;

identify one or more additional search terms related to the selected search result;

adding the one or more additional search terms to the search terms of the first search to initiate a next search; and

returning one or more search results of the next search, the search results similar to the selected search result

44. The method of claim 40, further comprising:

receiving a selection of a search result;

identifying a plurality of terms related to the selected search result and that belong to an associated domain dictionary;

sorting the terms by average affinity;

selecting a predetermined number of terms with higher average affinity; and

adding the selected terms to the search terms of the first search to initiate a next search.

45. The method of claim 40, further comprising:

receiving a selection of a search result;

identifying a plurality of terms related to the selected search result and that are current search suggestions;

sorting the terms by average affinity;

selecting a predetermined number of terms with higher average affinity; and

adding the selected terms to the search terms of the first search to initiate a next search.

46. The method of claim 40, further comprising:

receiving a selection of a search result to initiate a tagging mode, the selection made by clicking on the search result; and

entering a tagging mode.

47. The method of claim 40, further comprising:

generating a plurality of suggested tags for a search result;

initiating display of the suggested tags at the search suggestions window;

receiving a selection of a suggested tag, the selection made by clicking on the suggested tag; and

tagging the search result with the selected tag.

48. The method of claim 40, further comprising:

receiving a selection of a suggested tag, the selection made by clicking on the suggested tag; and

adding the suggested tag to the search terms to initiate a next search.

49. The method of claim 40, further comprising:

receiving a selection of a search result, the selection made by clicking on the search result;

adding the selected search result to the search terms to initiate a next search; and

returning one or more search results of the next search.

50. The method of claim 40, a search result comprising an image or video.