ID persistence through normalization

• US 7,991,797 B2
• Filed: 02/17/2006
• Issued: 08/02/2011
• Est. Priority Date: 02/17/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Betz, Jonathan T., Hogue, Andrew W.
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Rahman; Sabana
• Application Number:
  US11/356,842
• Publication Number:
  US 20070198577A1
• Time in Patent Office: 1,992 Days
• Field of Search: 707/103.R, 706/48, 706/50
• US Class Current: 707/803
• CPC Class Codes: G06F 16/2272 Management thereof

Abstract

A system and method for maintaining persistent object identifiers across versions of a collection of data. According to one embodiment of the present invention, a first collection of objects is compared to a second collection of objects. If an object in the first collection matches an object in the second collection, a reference is added to the object in the first collection referring to the object in the second collection, allowing the identifier to persist in both collections of objects. Additionally, according to one embodiment of the present invention, the data (or “facts”) associated with the object from the first collection are moved to the object from the second collection. In this way, data associated with matching objects is combined between two collections of objects while maintaining persistent object identifiers.

Claims

1. A computer-implemented method for maintaining object ID persistence in a collection of data, 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;

selecting a first object from the collection of data having a first object ID, wherein a first fact comprising an associated object ID is associated with the first object, the collection of data includes a plurality of objects and a plurality of facts associated with the objects, each fact comprises an attribute-value pair, and the plurality of facts are extracted from a plurality of web documents;

selecting a second object from the collection of data having a second object ID;

performing a heuristic comparison on the first object and the second object to determine if the first object and the second object refer to a same entity;

responsive to determining that the first object and the second object refer to the same entity,

associating with the first object a forwarding reference to the second object, so that the second object can be referenced using the first object ID;

dissociating the first fact from the first object; and

associating the first fact with the second object by setting the associated object ID of the first fact to the second object ID, so that the first fact is merged with facts for the second object; and

responsive to receiving an external reference to the first object,

identifying that the first object includes a forwarding reference to the second object; and

retrieving the second object.

2. The method of claim 1, wherein a second fact is associated with the second object, and wherein determining if the first object and the second object refer to the same entity comprises comparing the first fact to the second fact to determine if the first object matches the second object.

3. The method of claim 2, wherein the first fact is compared to the second fact by a heuristic comparison function.

4. The method of claim 2, further comprising:

responsive to determining that the first object matches the second object, associating with the first object a forwarding reference to the second object, so that the second fact may be accessed by referring to the first object ID.

5. The method of claim 1, wherein a first plurality of facts is associated with the first object and a second plurality of facts is associated with the second object, and wherein determining if the first object and the second object refer to the same entity comprises comparing the first plurality of facts to the second plurality of facts to determine if the first object matches the second object.

6. The method of claim 1, wherein a forwarding reference to the first object is associated with a third object, the method further comprising:

responsive to determining that the first object and the second object refer to the same entity, modifying the forwarding reference to the first object so that it points to the second object.

7. The method of claim 1, wherein the first object is contained in a first collection of data and wherein the second object is not contained in the first collection of data.

8. The method of claim 1, wherein the second object is contained in a first collection of data and wherein the first object is not contained in the first collection of data.

9. The method of claim 1, wherein the first object is contained in a first collection of data, and wherein the steps are performed by a janitor operating before a build of the first collection of data.

10. The method of claim 1, wherein the second object is contained in a first collection of data, and wherein the steps are performed by a janitor operating before a build of the first collection of data.

11. A computer readable storage medium for maintaining object ID persistence in a collection of data, the computer readable storage medium storing one or more programs for execution by one or more processors in a computer system, the one or more programs comprising:

instructions for selecting a first object from the collection of data having a first object ID, wherein a first fact comprising an associated object ID is associated with the first object, the collection of data includes a plurality of objects and a plurality of facts associated with the objects, each fact comprises an attribute-value pair, and the plurality of facts are extracted from a plurality of web documents;

instructions for selecting a second object from the collection of data having a second object ID;

instructions for performing a heuristic comparison on the first object and the second object to determine if the first object and the second object refer to a same entity;

instructions for, responsive to determining that the first object and the second object refer to the same entity,

associating with the first object a forwarding reference to the second object, so that the second object can be referenced using the first object ID;

dissociating the first fact from the first object; and

associating the first fact with the second object by setting the associated object ID of the first fact to the second object ID, so that the first fact is merged with facts for the second object; and

program code for, responsive to receiving an external reference to the first object,

identifying that the first object includes a forwarding reference to the second object; and

retrieving the second object.

12. A system for maintaining object ID persistence in a collection of data, comprising:

one or more processors;

memory; and

one or more programs stored in the memory, the one or more programs comprising instructions to;

select a first object from the collection of data having a first object ID, wherein a first fact comprising an associated object ID is associated with the first object, the collection of data includes a plurality of objects and a plurality of facts associated with the objects, each fact comprises an attribute-value pair and the plurality of facts are extracted from a plurality of web documents;

select a second object from the collection of data having a second object ID;

perform a heuristic comparison on the first object and the second object to determine if the first object and the second object refer to a same entity; and

responsive to determining that the first object and the second object refer to the same entity,

associate with the first object a forwarding reference to the second object, so that the second object can be referenced using the first object ID;

dissociate the first fact from the first object; and

associate the first fact with the second object by setting the associated object ID of the first fact to the second object ID, so that the first fact is merged with facts for the second object; and

responsive to receiving an external reference to the first object,

identify that the first object includes a forwarding reference to the second object; and

retrieve the second object.

13. A computer-implemented method for maintaining object ID persistence in a collection of data, 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;

selecting a first set of one or more facts from the collection of data associated with a first object ID, the collection of data includes a plurality of objects and a plurality of facts associated with the objects, each fact comprises an attribute-value pair and the plurality of facts are extracted from a plurality of web documents;

selecting a second set of one or more facts from the collection of data associated with a second object ID;

performing a heuristic comparison on the first set of one or more facts and the second set of one or more facts to determine if the first set of one or more facts associated with the first object ID and the second set of one or more facts associated with the second object ID refer to a same entity;

responsive to determining that the first set of one or more facts associated with the first object ID and the second set of one or more facts associated with the second object ID refer to a same entity and;

associating with the first object ID a forwarding reference to the second object ID, so that the second set of one or more facts associated with the second object ID can be referenced using the first object ID, and dissociating the first set of one or more facts from the first object ID; and

associating the first fact with the second object by setting the associated object ID of the first fact to the second object ID, so that the first fact is merged with facts for the second object; and

responsive to receiving an external reference to the first object ID, identifying that the first object ID includes a forwarding reference to the second object ID and retrieving the second object ID.

14. The method of claim 13, wherein determining if the first set of one or more facts associated with the first object ID and the second set of one or more facts associated with the second object ID refer to a same entity comprises comparing a fact from the first set of one or more facts to a fact from the second set of one or more facts.

15. The method of claim 13, further comprising:

responsive to determining that the first set of one or more facts associated with the first object ID and the second set of one or more facts associated with the second object ID refer to the same entity, associating with the first object ID a forwarding reference to the second object ID, so that the second set of one or more facts associated with the second object ID may be accessed by referring to the first object ID.

16. The method of claim 13, additionally comprising:

responsive to determining that that the first set of one or more facts associated with the first object ID and the second set of one or more facts associated with the second object ID refer to the same entity, associating a fact from the set of one or more facts associated with the first object ID with the second object ID.

17. The method of claim 13, wherein a forwarding reference to the first object ID is associated with a third object ID, the method further comprising:

responsive to determining that the first set of one or more facts associated with the first object ID and the second set of one or more facts associated with the second object ID refer to the same entity, modifying the forwarding reference to the first object ID so that it points to the second object ID.

18. A computer-implemented method for maintaining object ID persistence in a collection of data, 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;

performing a heuristic comparison on the first object and the second object to determine if a first object from the collection of data having a first object ID and a second object from the collection of data having a second object ID refer to a same entity, wherein a first fact comprising an associated object ID is associated with the first object, the collection of data includes a plurality of objects and a plurality of facts associated with the objects, each fact comprises an attribute-value pair and the plurality of facts are extracted from a plurality of web documents; and

responsive to determining that the first object and the second object refer to the same entity,

associating with the first object a forwarding reference to the second object, so that the second object can be referenced using the first object ID;

dissociating the first fact from the first object; and

associating the first fact with the second object by setting the associated object ID of the first fact to the second object ID, so that the first fact is merged with facts for the second object; and

responsive to receiving an external reference to the first object,

identifying that the first object includes a forwarding reference to the second object; and

retrieving the second object.