Robust discovery of entity synonyms using query logs

• US 8,745,019 B2
• Filed: 06/04/2012
• Issued: 06/03/2014
• Est. Priority Date: 03/05/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cheng, Tao, Chakrabarti, Kaushik, Chaudhuri, Surajit, Xin, Dong
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US13/487,260
• Publication Number:
  US 20130232129A1
• Time in Patent Office: 729 Days
• Field of Search: 707/608, 707/687, 707/705, 707/790, 707/813, 707/821
• US Class Current: 707/705
• CPC Class Codes: G06F 16/3338 Query expansion

Abstract

A similarity analysis framework is described herein which leverages two or more similarity analysis functions to generate synonyms for an entity reference string r_e. The functions are selected such that the synonyms that are generated by the framework satisfy a core set of synonym-related properties. The functions operate by leveraging query log data. One similarity analysis function takes into consideration the strength of similarity between a particular candidate string s_e and an entity reference string r_e even in the presence of sparse query log data, while another function takes into account the classes of s_e and r_e. The framework also provides indexing mechanisms that expedite its computations. The framework also provides a reduction module for converting long entity reference strings into shorter strings, where each shorter string (if found) contains a subset of the terms in its longer counterpart.

Claims

1. A method, implemented by one or more computer processors, comprising:

providing an entity reference string r_e that is associated with an entity;

providing a set of candidate strings S_e, comprising at least one candidate string s_e;

generating, using query log data, similarity score information for respective pairs of individual candidate strings of the set of candidate strings S_e and the entity reference string r_e using at least two similarity analysis functions; and

determining, using the similarity score information, whether the individual candidate strings are valid synonyms of the entity reference string r_e, where a valid synonym refers to the entity and satisfies a core set of synonym-related properties jointly provided by said at least two similarity analysis functions.

4. The method of claim 1, wherein a first subset of the synonym-related properties satisfied by a first similarity analysis function of the at least two similarity analysis functions differs from a second subset of synonym-related properties satisfied by a second similarity analysis function of the at least two similarity analysis functions.

5. The method of claim 1, wherein at least one synonym-related property in the core set of synonym-related properties is a symmetry property, wherein a pair (r_e, s_e) satisfies the symmetry property when both the at least one candidate string s_e is considered similar to the entity reference string r_e, and the entity reference string r_e is considered similar to the at least one candidate string s_e.

6. The method of claim 1, wherein at least one synonym-related property in the core set of synonym-related properties is a strength-of-similarity property, wherein a pair (r_e, s_e) satisfies the strength-of-similarity property when a strength of similarity between the entity reference string r_e and the at least one candidate string s_e exceeds a prescribed strength-related threshold.

7. The method of claim 1, wherein at least one synonym-related property in the core set of synonym-related properties is a relatedness-of-class property, wherein a pair (r_e, s_e) satisfies the relatedness-of-class property when the entity reference string r_e and the at least one candidate string s_e correspond to a same class of strings.

8. The method of claim 1, further comprising generating the set of candidate strings S_e by:

determining, using the query log data, a set of documents D that have been selected in response to submitting the entity reference string r_e as a query; and

determining, using the query log data, a set of queries that have been submitted and which have resulted in selection of at least one document in the set of documents D, the set of queries comprising the set of candidate strings S_e.

9. The method of claim 1, further comprising converting the entity reference string r_e to a shorter entity reference string r_e′

, wherein the shorter entity reference string r_e′

contains a subset of terms found in the entity reference string r_e.

11. The method of claim 8, wherein said generating the similarity score information comprises generating a first pseudo-document similarity score Score_pdsim(s_e→

r_e) for the individual candidate strings which describes a strength of relatedness of the individual candidate strings to the entity reference string r_e, and a second pseudo-document similarity score Score_pdsim(r_e→

s_e) for the individual candidate strings which describes a strength of relatedness of the entity reference string r_e to the individual candidate strings.

12. The method of claim 8, wherein said generating comprises generating a query context similarity score Score_qcsim for the individual candidate strings by:

receiving context information for the entity reference string r_e, the context information for the entity reference string r_e identifying words used in conjunction with the entity reference string r_e when the entity reference string r_e has been submitted as the query;

receiving context information for the individual candidate strings, the context information for the individual candidate strings identifying words used in conjunction with the individual candidate strings when the individual candidate strings have been submitted as other queries; and

generating the query context similarity score Score_qcsim for the individual candidate strings using the context information for the entity reference string r_e and the context information for the individual candidate strings.

13. The method of claim 9, wherein said converting comprises using a fuzzy-matching reduction function to generate the shorter entity reference string r_e′

from the entity reference string r_e.

14. The method of claim 9, wherein said converting comprises:

submitting the entity reference string r_e to a search engine;

receiving a set of documents D which match the entity reference string r_e;

finding an initial set of queries, using the query log data, that have resulted in selection of individual documents in the set of documents D, wherein individual queries of the initial set of queries include the subset of terms found in the entity reference string r_e; and

using similarity analysis to find at least one query in the initial set of queries that is sufficiently related to the entity reference string r_e, providing that said at least one query can be found, said at least one query corresponding to the shorter entity reference string r_e′

.

16. The method of claim 11, wherein said generating the first pseudo-document similarity score Score_pdsim(s_e→

r_e) for the individual candidate strings comprises;

receiving a set of pseudo-documents PD, individual pseudo-documents pdoc in the set of pseudo-documents PD corresponding to a document d in the set of documents D, and individual pseudo-documents pdoc containing a set of terms found in queries that have been submitted and which have resulted in the selection of the document d;

determining, for the individual candidate strings, a number of the individual pseudo-documents pdoc that contain all of the terms in the individual candidate strings; and

generating the first pseudo-document similarity score Score_pdsim(s_e→

r_e) for the individual candidate strings using said number.

18. The method of claim 16, wherein said determining the number of the individual pseudo-documents pdoc comprises:

generating a PD inverted index that relates the individual pseudo-documents pdoc to terms found in the set of candidate strings S_e;

generating a s_e inverted index that relates the individual candidate strings to terms found in the set of candidate strings S_e;

generating a CD matrix that identifies, for individual pairs of a particular pseudo-document pdoc and a particular candidate string s_e, a number of terms in the particular candidate string s_e that are found in the particular pseudo-document pdoc; and

determining the number of the individual pseudo-documents pdoc using the CD matrix.

19. The method of claim 16, wherein said determining the number of the individual pseudo-documents pdoc is performed in a distributed manner using a plurality of computational nodes.

2. A computer-implemented system comprising:

a similarity analysis framework including at least two similarity analysis modules and a filtering module, wherein;

the similarity analysis framework is configured to provide an entity reference string that is associated with an entity and provide a set of candidate strings,

the at least two similarity analysis modules are configured to generate, using query log data, similarity score information for respective pairs of the entity reference string and individual candidate strings of the set of candidate strings, and

the filtering module is configured to determine, using the similarity score information, whether the individual candidate strings are valid synonyms of the entity reference string, where a valid synonym refers to the entity and satisfies a core set of synonym-related properties jointly provided by said at least two similarity analysis modules; and

a processor that executes computer-executable instructions associated with the similarity analysis framework.

10. The system of claim 2, wherein the similarity analysis framework is further configured to generate the set of candidate strings by:

determining, using the query log data, a set of documents that have been selected in response to submitting the entity reference string as a query; and

determining, using the query log data, a set of queries that have been submitted and which have resulted in selection of at least one document in the set of documents, the set of queries comprising the set of candidate strings.

15. The system of claim 10, the at least two similarity analysis modules further configured to generate the similarity score information by generating a first pseudo-document similarity score for the individual candidate strings which describes a strength of relatedness of the individual candidate strings to the entity reference string, and a second pseudo-document similarity score for the individual candidate strings which describes a strength of relatedness of the entity reference string to the individual candidate strings.

17. The system of claim 15, wherein said generating the first pseudo-document similarity score for the individual candidate strings comprises:

receiving a set of pseudo-documents, an individual pseudo-document in the set of pseudo-documents corresponding to a respective document in the set of documents, and the individual pseudo-document containing a set of terms found in queries that have been submitted and which have resulted in the selection of the respective document;

determining, for the individual candidate strings, a number of pseudo-documents that contain all of the terms of the set in the individual candidate strings; and

generating the first pseudo-document similarity score for the individual candidate strings using said number.

20. The system of claim 17, wherein said determining the number of pseudo-documents comprises:

generating an inverted index that relates pseudo-documents to terms found in the set of candidate strings;

generating another inverted index that relates candidate strings to terms found in the set of candidate strings;

generating a matrix that identifies, for individual pairs of a particular pseudo-document and a particular candidate string, a number of terms in the particular candidate string that are found in the particular pseudo-document; and

determining the number of pseudo-documents using the matrix.

3. Computer readable storage media storing computer readable instructions that, when executed by one or more processing devices, cause the one or more processing devices to perform acts comprising:

providing an entity reference string that is associated with an entity;

providing a set of candidate strings;

generating, using query log data, similarity score information for respective pairs of the entity reference string and individual candidate strings of the set of candidate strings using at least two similarity analysis functions; and

determining, using the similarity score information, whether the individual candidate strings are valid synonyms of the entity reference string, where a valid synonym refers to the entity and satisfies a core set of synonym-related properties jointly provided by said at least two similarity analysis functions.