Learning synonymous object names from anchor texts

• US 8,738,643 B1
• Filed: 08/02/2007
• Issued: 05/27/2014
• Est. Priority Date: 08/02/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Czuba, Krzysztof, Betz, Jonathan T., Reynar, Jeffrey C.
• Primary Examiner(s): Badawi, Sherief
• Assistant Examiner(s): Mitiku, Berhanu
• Application Number:
  US11/833,180
• Time in Patent Office: 2,490 Days
• Field of Search: None
• US Class Current: 707/767
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/134 Hyperlinking

Abstract

A repository contains objects representing entities. The objects also include facts about the represented entities. The facts are derived from source documents. A synonymous name of an object is determined by identifying a source document from which one or more facts of the entity represented by the object were derived, identifying a plurality of linking documents that link to the source document through hyperlinks, each hyperlink having an anchor text, processing the anchor texts in the plurality of linking documents to generate a collection of synonym candidates for the entity represented by the object, and selecting a synonymous name for the entity represented by the object from the collection of synonym candidates.

Claims

1. A method of determining a synonymous name for an entity represented by an object stored in a fact repository, comprising:

at a server having a plurality of processors and memory storing the repository and programs configured for execution by the processors, wherein the repository includes a plurality of facts extracted from web documents, wherein a subset of the facts is associated with the object, and wherein the object has an object name associated with the entity,

identifying a source document from which one or more of the subset of facts of the entity represented by the object were derived;

identifying a plurality of linking documents having hyperlinks to the source document, each hyperlink having an anchor text;

generating a collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents;

selecting a synonymous name for the entity represented by the object from the collection of synonym candidates, wherein selecting the synonymous name for the entity represented by the object from the collection of synonym candidates further comprises;

determining a score for each synonym candidate in the collection of synonym candidates based on a score function, the score function taking into account;

a frequency of occurrence of the synonym candidate in the collection of synonym candidates, and

a proportion of the synonym candidate in the collection of synonym candidates;

selecting the synonymous name for the entity represented by the object from the collection of synonym candidates based on their scores; and

storing the synonymous name in the repository in association with the object in addition to the object name.

2. The method of claim 1, wherein identifying the source document further comprises:

identifying a list of source documents from which one or more facts of the entity represented by the object were derived;

removing from the list identifiers of source documents from which one or more facts of another entity were derived from the list; and

identifying the source document from the list of source documents.

3. The method of claim 1, wherein generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprises:

normalizing the anchor texts in the plurality of linking documents; and

generating the collection of synonym candidates for the entity using the normalized anchor texts.

4. The method of claim 3, wherein normalizing the anchor texts in the plurality of linking documents further comprises:

identifying a language of one of the plurality of linking documents; and

applying normalization rules for the language to normalize the anchor text in the one of the plurality of linking documents.

5. The method of claim 1, wherein generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprises:

extracting a noun phrase from one of the anchor texts in the plurality of linking documents; and

generating the collection of synonym candidates for the entity using the extracted noun phrase.

6. The method of claim 1, wherein generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprises:

removing a prefix or a suffix from the anchor texts in the plurality of linking documents.

7. The method of claim 1, wherein generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprises:

matching an anchor text with a black list of texts; and

responsive to detecting a match of the anchor text with the black list, removing the anchor text from the collection of synonym candidates for the entity represented by the object.

8. The method of claim 1, wherein generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprises:

matching an anchor text with a white list of texts; and

responsive to detecting a match of the anchor text with the white list, adding the anchor text into the collection of synonym candidates for the entity represented by the object.

9. The method of claim 1, wherein selecting the synonymous name for the entity represented by the object from the collection of synonym candidates further comprises:

selecting a synonym candidate occurring at a frequency in the collection of synonym candidates no less than a minimum threshold as the synonymous name for the entity represented by the object.

10. The method of claim 9, further comprising:

responsive to a synonym candidate occurring at a frequency in the collection of synonym candidates less than the minimum threshold, adding the synonym candidate into a black list of texts.

11. The method of claim 1, wherein selecting the synonymous name for the entity represented by the object from the collection of synonym candidates further comprises:

selecting a synonym candidates occurring at a frequency in the collection of synonym candidates no more than a maximum threshold as the synonymous name for the entity represented by the object.

12. The method of claim 11, further comprising:

responsive to a synonym candidate occurring at a frequency in the collection of synonym candidates more than the maximum threshold, adding the synonym candidate into a black list of texts.

13. The method of claim 1, wherein selecting the synonymous name for the entity represented by the object from the collection of synonym candidates further comprises:

determining quality for the plurality of linking documents; and

selecting the synonymous name for the entity represented by the object from the collection of synonym candidates based on the quality of the linking document having the anchor text from which the synonymous name was generated.

14. The method of claim 1, wherein

the score function further takes into account at least one of the following factors:

a quality of the linking document having the anchor text from which the synonym candidate was generated,

whether the synonym candidate has a match in a white list,

whether the synonym candidate has a match in a black list, and

whether the synonym candidate is properly capitalized.

15. A system for determining a synonymous name for an entity represented by an object stored in a repository, comprising:

a processor for executing programs;

memory for storing the repository and the programs, wherein the repository includes a plurality of facts extracted from web documents, wherein a subset of the facts is associated with the object, and wherein the object has an object name associated with the entity; and

a subsystem executable by the processor, the subsystem including;

instructions for identifying a source document from which one or more of the subset of facts of the entity represented by the object were derived;

instructions for identifying a plurality of linking documents having hyperlinks to the source document, each hyperlink having an anchor text;

instructions for generating a collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents;

instructions for selecting a synonymous name for the entity represented by the object from the collection of synonym candidates, wherein selecting the synonymous name for the entity represented by the object from the collection of synonym candidates further comprises;

determining a score for each synonym candidate in the collection of synonym candidates based on a score function, the score function taking into account;

a frequency of occurrence of the synonym candidate in the collection of synonym candidates, and

a proportion of the synonym candidate in the collection of synonym candidates

selecting the synonymous name for the entity represented by the object from the collection of synonym candidates based on their scores; and

instructions for storing the synonymous name in the repository in association with the object in addition to the object name.

16. The system of claim 15, wherein the instructions for identifying a source document further comprises:

instructions for identifying a list of source documents from which one or more facts of the entity represented by the object were derived;

instructions for removing from the list identifiers of source documents from which one or more facts of another entity were derived from the list; and

instructions for identifying the source document from the list of source documents.

17. The system of claim 15, wherein the instructions for generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprise:

instructions for normalizing the anchor texts in the plurality of linking documents; and

instructions for generating the collection of synonym candidates for the entity using the normalized anchor texts.

21. The system of claim 17, wherein the instructions for normalizing the anchor texts in the plurality of linking documents further comprises:

instructions for identifying a language of one of the plurality of linking documents; and

instructions for applying normalization rules for the language to normalize the anchor text in the one of the plurality of linking documents.

22. The system of claim 15, wherein the instructions for generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprise:

instructions for extracting a noun phrase from one of the anchor texts in the plurality of linking documents; and

instructions for generating the collection of synonym candidates for the entity using the normalized anchor texts.

23. The system of claim 15, wherein the instructions for generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprise:

instructions for removing a prefix or a suffix from the anchor texts in the plurality of linking documents.

24. The system of claim 15, wherein the instructions for generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprise:

instructions for matching an anchor text with a black list of texts; and

instructions for responsive to detecting a match of the anchor text with the black list, removing the anchor text from the collection of synonym candidates for the entity represented by the object.

25. The system of claim 15, wherein the instructions for generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprise:

instructions for matching an anchor text with a white list of texts; and

instructions for responsive to detecting a match of the anchor text with the white list, adding the anchor text into the collection of synonym candidates for the entity represented by the object.

26. The system of claim 15, wherein the instructions for selecting the synonymous name for the entity represented by the object from the collection of synonym candidates further comprises:

instructions for determining quality for the plurality of linking documents; and

instructions for selecting the synonymous name for the entity represented by the object from the collection of synonym candidates based on the quality of the linking document having the anchor text from which the synonymous name was generated.

27. The system of claim 15, wherein

the score function further takes into account at least one of the following factors:

a quality of the linking document having the anchor text from which the synonym candidate was generated,

whether the synonym candidate has a match in a white list,

whether the synonym candidate has a match in a black list, and

whether the synonym candidate is properly capitalized.

18. A computer program product stored on a non-transitory computer readable storage medium and for use in conjunction with a computer system, the computer program product comprising a computer program mechanism embedded therein, the computer program mechanism including:

instructions for identifying a source document from which one or more facts of an entity represented by an object were derived, the facts and the object being stored in a repository that can be accessed by the computer system, the facts being associated with the object, and the object having an object name associated with the entity;

instructions for identifying a plurality of linking documents having hyperlinks to the source document, each hyperlink having an anchor text;

instructions for generating a collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents;

instructions for selecting a synonymous name for the entity represented by the object from the collection of synonym candidates, wherein selecting the synonymous name for the entity represented by the object from the collection of synonym candidates further comprises;

determining a score for each synonym candidate in the collection of synonym candidates based on a score function, the score function taking into account;

a frequency of occurrence of the synonym candidate in the collection of synonym candidates, and

a proportion of the synonym candidate in the collection of synonym candidates;

selecting the synonymous name for the entity represented by the object from the collection of synonym candidates based on their scores; and

instructions for storing the synonymous name in the repository in association with the object in addition to the object name.

19. The computer program product of claim 18, wherein the instructions for identifying a source document further includes:

instructions for identifying a list of source documents from which one or more facts of the entity represented by the object were derived;

instructions for removing from the list identifiers of source documents from which one or more facts of another entity were derived from the list; and

instructions for identifying the source document from the list of source documents.

20. The computer program product of claim 18, wherein the instructions for generating the collection of synonym candidates for the entity using the anchor texts in the plurality of linking documents further comprise:

instructions for normalizing the anchor texts in the plurality of linking documents; and

instructions for generating the collection of synonym candidates for the entity based on the name of the object using the normalized anchor texts.