IDENTIFYING SYNONYMS OF ENTITIES USING WEB SEARCH

• US 20100293179A1
• Filed: 05/14/2009
• Published: 11/18/2010
• Est. Priority Date: 05/14/2009
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Ganti, Venkatesh, Xin, Dong
• Application Number:
  US12/465,832
• Publication Number:
  US 20100293179A1
• Time in Patent Office: Days
• US Class Current: 707/759
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation

Abstract

Identifying synonyms of entities using web search results is disclosed herein. In some aspects, a candidate string of tokens of an entity name is selected as a search term. The search term is transmitted by a server to a search engine, which in turn, transmits search results back to the server after performing a search. The server analyzes the search results, generates a score based on the search results, and then determines a status (synonym or not a synonym) of the candidate string based on the score. In further aspects, additional candidate strings are designated as synonyms or not synonyms based on status of the searched candidate string by using relationships of a lattice formed from all possible candidate strings of the entity name.

Claims

1. A method of identifying synonyms of an entity name, the method comprising:

transmitting a search term to a web server, the search term being a candidate string selected from tokens of the entity name

receiving a plurality of search results from the web server, the search results including at least one of a title, a uniform resource locator (URL), and a snippet of content of a web page;

identifying tokens of the entity name that are included in the plurality of search results;

generating a score for the plurality of search results based on the identified tokens;

comparing the generated score to a threshold value used to indicate whether the candidate string is a synonym of the entity name; and

storing the candidate string as a synonym when the generated score at least reaches the threshold value.

2. The method as recited in claim 1, further comprising using the synonyms in the synonym list to retrieve documents associated with the entity name.

3. The method as recited in claim 1, wherein the generating the score includes counting unique instances of the identified tokens from the search results and assigning a numerical value to the search result based on the count of the unique instances of the identified tokens.

4. The method as recited in claim 1, further comprising generating a lattice for the candidate strings of the entity name, wherein the lattice relates incremental subsets and supersets of each candidate string a related candidate string.

5. The method as recited in claim 4, further comprising:

designating an additional candidate string that is a superset of the candidate string as a synonym of the entity name when the candidate string is a synonym; and

designating an additional candidate string that is a subset of the candidate string as not a synonym of the entity name when the candidate string is not a synonym.

6. The method as recited in claim 5, further comprising:

determining a cut of the lattice by identifying a minimum number of specific candidate strings that can be searched to determine all of the synonyms of the entity name using at least one of a depth-first schedule or a maximum-benefit schedule; and

selecting candidate strings of a subsequent entity name from a profile grouping of similarly structured entity names to efficiently determine the cut.

7. One or more computer-readable media storing computer-executable instructions that, when executed on one or more processors, causes the one or more processors to perform acts comprising:

receiving search results for a candidate string from a search engine, the candidate string selected from a unique combination of tokens of an entity name;

generating a score for the candidate string based on instances of tokens present in the search results to determine a status of the candidate string of the entity name, the status being at least one of a synonym or not a synonym; and

storing the candidate string as a synonym when the score at least reaches a threshold value.

8. The one or more computer-readable media as recited in claim 7, wherein the acts further comprise pruning at least one candidate string of the entity name after the status of the searched candidate string is determined, wherein the pruning determines the status of the at least one candidate string by exploiting a lattice of the candidate strings of the entity name by:

designating the at least one candidate string that is a superset of the candidate string as a synonym of the entity name when the candidate string is a synonym; and

designating the at least one candidate string that is a subset of the candidate string as not a synonym of the entity name when the candidate string is not a synonym.

9. The one or more computer-readable media as recited in claim 8, wherein the lattice includes layers of candidate strings that are linked to at least one of a subset or a superset of candidate strings in the layers.

10. The one or more computer-readable media as recited in claim 8, wherein the acts further comprise determining a cut of the lattice by identifying a minimum number of specific candidate strings that need to be scored and pruned to determine all the synonyms of the entity name using at least one of a depth-first schedule or a maximum-benefit schedule.

11. The one or more computer-readable media as recited in claim 10, wherein the acts further comprise:

analyzing a subsequent entity name to determine synonyms of the subsequent entity name; and

selecting subsequent candidate strings of the subsequent entity name to search via a search engine based on the cut.

12. The one or more computer-readable media as recited in claim 7, wherein the acts further comprise selecting another candidate string for determination of the status until all candidate strings of the entity name have been identified as a synonym or not a synonym.

13. The one or more computer-readable media as recited in claim 7, wherein the acts further comprise outputting a synonym list that includes all of the synonyms of the entity name.

14. A method, comprising:

creating a lattice of candidate strings selected from tokens of an entity name to establish a hierarchical relationship between the candidate strings;

sending a first candidate string of the lattice to a web search engine to perform a web search, the web search to return web search results;

generating a score based on instances of the tokens of the entity name included in the web search results;

designating the first candidate string as a either a synonym of the entity name when the score at least reaches a threshold value or as not a synonym; and

updating the lattice with the status of the first candidate string.

15. The method as recited in claim 14, further comprising designating a second candidate string in the lattice as either a synonym or not a synonym based on the relationship of the second candidate string to the first candidate string.

16. The method as recited in claim 15, wherein the second candidate string is designated as a synonym when the second candidate string is a superset of the first candidate string and the first candidate string is a synonym of the entity name.

17. The method as recited in claim 16, wherein the second candidate string is designated as not a synonym when the second candidate string is a subset of the first candidate string and the first candidate string is not determined to be a synonym of the entity name.

18. The method as recited in claim 17, further comprising identifying a cut of the lattice using at least one of a depth-first schedule or a maximum-benefit schedule, the cut defined by a minimum number of specific candidate strings to be used as search terms in a search via a search engine to determine all of the synonyms of the entity name, the cut being usable by a similar entity name to expedite synonym identification of the similar entity name.

19. The method as recited in claim 14, wherein generating the score is based on the quantity of unique tokens in the entity name, and wherein the web search results includes a snippet of text from a document, the snippet including at least one token from the first candidate string.

20. The method as recited in claim 14, further comprising:

populating a synonym list with the designated first candidate string as the synonym, and

storing the synonym list.