Generating synonyms based on query log data

• US 9,092,517 B2
• Filed: 09/23/2008
• Issued: 07/28/2015
• Est. Priority Date: 09/23/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Paparizos, Stelios, Cheng, Tao, Lauw, Hady W.
• Primary Examiner(s): Arjomandi, Noosha
• Application Number:
  US12/235,635
• Publication Number:
  US 20100082657A1
• Time in Patent Office: 2,499 Days
• Field of Search: 707/706, 707/765, 707/766
• US Class Current: 1/1
• CPC Class Codes: G06F 16/374 Thesaurus

Abstract

An approach is described for generating synonyms to supplement at least one information item, such as, in one case, a set of related items. The approach can involve an expansion phase, a clean-up phase, and a reduction phase. In the expansion phase, the approach identifies, for each related item, a set of initial synonym candidates. In the clean-up phase, the approach removes noise from the set of initial synonym candidates (if such noise exists), to provide a set of filtered synonym candidate items. In the reduction phase, the approach ranks and applies a threshold (or thresholds) to the set of filtered synonym candidate items, to generate, for each information item, a set of selected synonyms. The approach uses query log data at various points in its operation. The selected synonyms can be used to improve the effectiveness of user searches.

Claims

1. A method performed by at least one computing device, the method comprising:

receiving an input information item;

identifying a set of page items that are returned when the input information item is used in a first query to at least one search module;

identifying one or more second queries, other than the first query, that have also been submitted to the at least one search module by users that accessed individual page items from the set of page items, wherein the one or more second queries are identified using query log data reflecting associations between the one or more second queries and the individual page items accessed by the users;

providing a set of initial synonym candidates that were previously submitted to the at least one search module in the one or more second queries by the users that accessed the individual page items from the set of page items;

removing noise from the set of initial synonym candidates, when the noise is present and can be identified, to obtain a set of filtered synonym candidates;

reducing the set of filtered synonym candidates to a set of selected synonyms that are deemed appropriate proxies for the input information item by;

obtaining metric factor values associated with the set of filtered synonym candidates, and

applying a threshold to the metric factor values to select the set of selected synonyms from the set of filtered synonym candidates; and

outputting synonym-expanded data that is formed based on the reducing.

2. The method of claim 1, wherein the method is performed with respect to each of a set of input information items, and wherein the set of input information items comprises a list of canonical information items associated with a common theme.

3. The method of claim 1, wherein the method is performed with respect to each of a set of input information items, wherein the set of input information items comprises at least part of a collection of data, the collection of data being at least partially structured.

4. The method of claim 1, wherein the identifying the set of page items comprises:

submitting the input information item to the at least one search module as the first query;

receiving, from the at least one search module, a set of initial page items in response to submitting the input information item; and

selecting the set of page items from the set of initial page items.

5. The method of claim 1, wherein the method is performed with respect to each of a set of input information items, and wherein the removing the noise comprises:

identifying, for each particular input information item of the set of input information items, at least one context-sensitive noise component within a corresponding set of initial synonym candidates associated with the particular input information item, when the at least one context-sensitive noise component is present and can be identified, the identifying of the at least one context-sensitive noise component being based on a determination that (a) the at least one context-sensitive noise component affects synonym candidates associated with two or more input information items in the set of input information items, and (b) the at least one context-sensitive noise component does not also affect canonical forms of the input information items; and

removing the at least one context-sensitive noise component from the corresponding set of initial synonym candidates associated with the particular input information item.

6. The method of claim 1, wherein the reducing comprises:

calculating the metric factor values associated with the set of filtered synonym candidates;

ranking the set of filtered synonym candidates based on the metric factor values to provide a set of ranked synonym candidates; and

applying the threshold such that each selected synonym of the set of selected synonyms is ranked above the threshold.

7. The method of claim 1, wherein the removing noise is performed after identifying the one or more second queries.

8. The method of claim 1, wherein the method is performed with respect to each of a set of input information items, and wherein the synonym-expanded data comprises the set of input information items in canonical form, supplemented to include, for each input information item of the set, an associated set of selected synonyms.

9. A computing device comprising:

at least one storage device storing instructions of a synonym-generating module; and

at least one processing device configured to execute the instructions,

wherein the instructions of the synonym generating module comprise;

an input module configured to receive an input information item;

an expansion module configured to expand the input information item into a set of initial synonym candidates based on query log data, the query log data reflecting associations between prior queries submitted by users and page items accessed by the users in response to the prior submitted queries, the set of initial synonym candidates corresponding to the prior submitted queries in the query log data;

a clean-up module configured to remove identifiable noise from the set of initial synonym candidates, wherein an output of the expansion module and the clean-up module comprises a set of filtered synonym candidates;

a reduction module configured to select a set of synonyms from the set of filtered synonym candidates based on the query log data to provide a set of selected synonyms that are deemed appropriate proxies for the input information item; and

an output module configured to output synonym-expanded data that is formed based on the set of synonyms selected by the reduction module,

wherein the reduction module comprises;

logic configured to obtain, based on the query log data, at least one metric factor associated with each filtered synonym candidate in the set of filtered synonym candidates to provide metric factors;

logic configured to rank the set of filtered synonym candidates based on the metric factors to obtain a set of ranked synonym candidates; and

logic configured to select the set of selected synonyms from the set of ranked synonym candidates based on the metric factors.

10. The computing device of claim 9, wherein the logic configured to select the set of selected synonyms comprises logic configured to apply a threshold to the set of ranked synonym candidates to identify the set of selected synonyms.

11. The computing device of claim 9, wherein the synonym-generating module operates on each of a set of input information items, and wherein the synonym-expanded data comprises the set of input information items in canonical form, supplemented to include, for each input information item, an associated set of selected synonyms.

12. A method performed by at least one computing device, the method comprising:

receiving an input information item;

identifying a set of page items that are returned as first search results when the input information item is used in a first query to at least one search module;

identifying one or more second queries, other than the first query, that have also been submitted to the at least one search module by users that accessed individual page items from the set of page items when the individual page items were returned as second search results for the one or more second queries, wherein the one or more second queries are identified using query log data reflecting that the one or more second queries were used by the users to access the individual page items;

providing a set of synonym candidates that were submitted to the at least one search engine in the one or more second queries by the users that accessed the individual page items from the set of page items;

identifying, from the set of synonym candidates, a set of selected synonyms that are deemed appropriate proxies for the input information item, wherein the set of selected synonyms are identified by;

obtaining metric factor values associated with the set of synonym candidates, and

at least one of applying a threshold to the metric factor values or ranking the synonym candidates according to the metric factor values; and

outputting the set of selected synonyms.

13. The method of claim 12, wherein the identifying the set of selected synonyms comprises filtering noise from the set of synonym candidates.

14. The method of claim 12, wherein the identifying the set of page items comprises submitting the first query to the at least one search module.

15. The method of claim 12, wherein the identifying the set of page items comprises identifying the set of page items using the query log data and the query log data indicates that the first query was previously submitted to the at least one search module.

16. The method of claim 12, wherein the set of selected synonyms are output to an individual user.

17. The method of claim 12, further comprising:

ranking the set of synonym candidates using the metric factor values; and

applying the threshold to the ranked set of synonym candidates to cull some of the set of synonym candidates that are not included in the set of selected synonyms.

18. The method of claim 12, further comprising:

deriving an individual metric factor value for an individual initial synonym candidate by determining a number of times that an individual page item was accessed by the users when the individual page item was returned as an individual second search result in response to an individual second query that includes the individual initial synonym candidate.

19. The method of claim 12, further comprising:

deriving an individual metric factor value for an individual initial synonym candidate by determining a number of times that an individual page item was clicked by the users when the individual page item was returned as an individual second search result in response to an individual second query that includes the individual initial synonym candidate.

20. The method of claim 12, wherein the metric factor values are obtained for at least two different metric factors for each of the synonym candidates.