Automatic object reference identification and linking in a browseable fact repository

• US 8,260,785 B2
• Filed: 02/17/2006
• Issued: 09/04/2012
• Est. Priority Date: 02/17/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hogue, Andrew W., Betz, Jonathan T.
• Primary Examiner(s): VO, TRUONG V
• Application Number:
  US11/356,837
• Publication Number:
  US 20070198481A1
• Time in Patent Office: 2,391 Days
• Field of Search: 707/3, 707/715, 707/741, 707/747
• US Class Current: 707/747
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links

Abstract

Links between facts associated with objects are automatically created and maintained in a fact repository. Names of objects are automatically identified in the facts, and collected into a list of names. The facts are then processed to identifying such names in the facts. Identified names are used as anchor text for search links. A search link includes a search query for a service engine which search the fact repository for facts associated with objects having the same name.

Claims

1. A computer implemented method comprising:

at a computer system including one or more processors and memory storing one or more programs, the one or more processors executing the one or more programs to perform the operations of;

storing a plurality of objects in a fact repository, wherein the objects are associated with facts, each fact having one or more terms;

modifying one or more of the facts in the fact repository, including automatically, without user intervention;

establishing a list of object names of objects in the fact repository, wherein the list of object names is stored as a hash table;

for a respective fact having multiple terms, comparing a respective phrase-identification metric for each of a plurality of different combinations of terms in the respective fact to identify one or more candidate phrases;

checking at least a subset of the candidate phrases against the list of object names, wherein checking the candidate phrases against the list of object names includes determining, for each respective candidate phrase whether a hash of the respective candidate phrase collides with a value in the hash table; and

for each fact in of a plurality of respective candidate phrases that match respective object names in the list of object names, constructing a respective search link for a respective fact corresponding to the respective candidate phrase, and storing the respective search link at a location associated with the respective fact in the fact repository, wherein selection of a representation of the respective search link invokes performance of a search query against the fact repository, the search query including one or more search criteria that include the respective object name corresponding to the respective candidate phrase; and

after modifying the facts in the fact repository, in accordance with a determination that one or more predefined criteria have been met, automatically repeating, without user intervention, the steps of establishing a list of object names from a plurality of name facts, identifying candidate phrases, checking candidate phrases against the list of object names and constructing and storing search links in the fact repository.

2. The method of claim 1, wherein constructing the respective search link for the respective fact further comprises:

using the respective candidate phrase in the respective fact as an anchor for the respective search link for the respective fact.

3. The method of claim 1, wherein identifying candidate phrases in a particular fact comprises:

forming a plurality of sequences of consecutive terms in the particular fact; and

testing each sequence of terms to determine whether the sequence is a phrase.

4. The method of claim 3, wherein testing each sequence of terms comprises:

determining whether an information gain of the sequence of terms exceeds a threshold.

5. The method of claim 3, wherein testing each sequence of terms comprises:

determining whether a probability of the sequence of terms exceeds a joint probability of the terms included in the sequence.

6. The method of claim 1, further comprising:

for each object name included in the list of object names, storing a category for an object associated with the object name; and

including in the search criteria of the search query an indication of the category of the object associated with the object name indicated in the search criteria.

7. The method of claim 1, further comprising:

for each object name included in the list of object names, storing an additional attribute for an object associated with the object name, along with a value of the attribute; and

including in the search criteria of the search query an indication of the additional attribute and the value of the attribute of the object associated with the object name indicated in the search criteria.

8. The method of claim 1, further comprising:

displaying an object including the respective fact, the object including the object name as the anchor of the respective search link for the respective fact;

responsive to receiving a selection of the respective search link, providing the search query to a search engine for retrieving objects having a name fact that matches the object name included in the search criteria of the respective search link;

receiving from the search engine at least one search result including an object having an object name that matches the object name included in the search criteria of the respective search link; and

displaying the received object.

9. The method of claim 1, wherein the one or more predefined criteria are met when a predetermined time period has elapsed since the fact repository was last modified.

10. The method of claim 1, wherein the one or more predefined criteria are met when a predetermined number of facts in the fact repository have been modified.

11. The method of claim 1, wherein the one or more predefined criteria are met when a predetermined number of new facts in the fact repository have been created.

12. The method of claim 1, wherein the phrase-identification metric for a plurality of different combinations of terms in the respective fact includes comparing the phrase-identification metric for a first term followed by a second term with the phrase-identification metric for a multi-term phrase including both the first term and the second term.

13. The method of claim 1, wherein:

the list of object names is stored as a hash table; and

checking the candidate phrases against the list of object names includes determining, for each respective candidate phrase whether a hash of the respective candidate phrase collides with a value in the hash table.

14. The method of claim 1, further comprising:

receiving a respective search query; and

in response to receiving the respective search query, returning representations of a plurality of objects matching the respective search query ordered in accordance with a relevance of the objects to the search query, wherein the relevance of an respective object to a search query is determined in accordance with a combination of the relevance of facts associated with the respective object to the search query.

15. The method of claim 14, wherein:

a respective representation of a respective object returned in response to receiving the respective search query includes representations of a plurality facts associated with the object; and

the facts in the respective representation of the respective object are selected and ordered in accordance with the relevance of the facts to the respective search query.

16. A system, comprising:

one or more processors;

memory; and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for;

storing a plurality of objects in a fact repository, wherein the objects are associated with facts, each fact having one or more terms;

modifying one or more of the facts in the fact repository, including automatically, without user intervention;

establishing a list of object names of objects in the fact repository, wherein the list of object names is stored as a hash table;

for a respective fact having multiple terms, comparing a respective phrase-identification metric for each of a plurality of different combinations of terms in the respective fact to identify one or more candidate phrases;

checking at least a subset of the candidate phrases against the list of object names, wherein checking the candidate phrases against the list of object names includes determining, for each respective candidate phrase whether a hash of the respective candidate phrase collides with a value in the hash table; and

for each of a plurality of respective candidate phrases that match respective object names in the list of object names, constructing a respective search link for a respective fact corresponding to the respective candidate phrase, and storing the respective search link at a location associated with the respective fact in the fact repository, wherein selection of a representation of the respective search link that invokes performance of a search against the fact repository, the search query including one or more search criteria that include the respective object name corresponding to the respective candidate phrase; and

after modifying the facts in the fact repository, in accordance with a determination that one or more predefined criteria have been met, automatically repeating, without user intervention, the steps of automatically establishing a list of object names from a plurality of name facts, identifying candidate phrases, checking candidate phrases against the list of object names, and automatically constructing and storing search links in the fact repository.

17. The system of claim 16, wherein the one or more predefined criteria are met when a predetermined time period has elapsed since the fact repository was last modified.

18. The system of claim 16, wherein the one or more predefined criteria are met when a predetermined number of facts in the fact repository have been modified.

19. The system of claim 16, the one or more predefined criteria are met when a predetermined number of new facts in the fact repository have been created.

20. A tangible computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a computer system with one or more processors, cause the computer system to:

store a plurality of objects in a fact repository, wherein the objects are associated with facts, each fact including one or more terms;

modify one or more of the facts in the fact repository, including automatically, without user intervention;

establish a list of object names from of objects in the fact repository,

wherein the list of object names is stored as a hash table;

for a respective fact having multiple terms, compare a respective phrase -identification metric for each of a plurality of different combinations of terms in the respective fact to identify one or more candidate phrases;

check at least a subset of the candidate phrases against the list of object names, wherein checking the candidate phrases against the list of object names includes determining, for each respective candidate phrase whether a hash of the respective candidate phrase collides with a value in the hash table; and

for each of a plurality of respective candidate phrases that match respective object names in the list of object names, construct and store a respective search link for a respective fact corresponding to the respective candidate phrase, and storing the respective search link at a location associated with the respective fact in the fact repository, wherein selection of a representation of the respective search link invokes performance of a search query against the fact repository, by a search query including one or more search criteria that include the respective object name corresponding to the respective candidate phrase; and

after modifying the facts in the fact repository, in accordance with a determination that one or more predefined criteria have been met, automatically repeat, without user intervention, the steps of automatically establishing a list of object names from a plurality of name facts, identifying candidate phrases, checking candidate phrases against the list of object names one or more facts of the plurality of facts including object names in the list of object names, and constructing and storing one-or more search links in the fact repository.

21. The computer readable storage medium of claim 20, wherein the one or more predefined criteria are met when a predetermined time period has elapsed since the fact repository was last modified.

22. The computer readable storage medium of claim 20, wherein the one or more predefined criteria are met when a predetermined number of facts in the fact repository have been modified.

23. The computer readable storage medium of claim 20, the one or more predefined criteria are met when a predetermined number of new facts in the fact repository have been created.