Two-phase construction of data graphs from disparate inputs

• US 9,342,622 B2
• Filed: 06/27/2013
• Issued: 05/17/2016
• Est. Priority Date: 06/27/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Segaran, Suresh Toby
• Primary Examiner(s): Shmatov, Alexey
• Application Number:
  US13/929,127
• Publication Number:
  US 20150006587A1
• Time in Patent Office: 1,055 Days
• Field of Search: 707/798
• US Class Current: 1/1
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Some implementations generate multiple views of a combined data graph from disparate data graph sources in two phases. A first phase may convert each source data graph into a reconciled data graph and a second phase may generate a combined data graph from the various reconciled data graphs. For example, a method may include generating a reconciled data graph for each of a plurality of source data graphs and determining selected sources identified by a graph view file. The selected sources may be a subset of the plurality of sources represented by the source data graphs. The method may also include generating a combined data graph using the reconciled data graphs that correspond with the selected sources, and generating search results using the combined data graph.

Claims

1. A computer system comprising:

memory storing a first source data graph in a first identifier space, the first identifier space uniquely identifying items in the first source;

memory storing a reconciled version of a second source data graph, the second source data graph being in a second identifier space and the reconciled version of the second source data graph being in a third identifier space, the second identifier space uniquely identifying items in the second source and the third identifier space uniquely identifying items to the computer system, wherein the first identifier space, the second identifier space, and the third identifier space differ from each other;

memory storing a master evidence file that maps the first identifier space to the third identifier space and the second identifier space to the third identifier space;

at least one processor; and

memory storing instructions that, when executed by the at least one processor cause the system to;

generate a reconciled version of the first source data graph by substituting identifiers in the first source data graph with identifiers in the third identifier space using the master evidence file,

store the reconciled version of the first source data graph, and

generate a combined data graph from the reconciled version of the first source data graph and the reconciled version of the second source data graph, the combined data graph being available for querying.

2. The system of claim 1, wherein generating the combined data graph includes:

determining that a first triple in the combined data graph is a duplicate of a second triple;

moving metadata about the first triple to the second triple; and

deleting the first triple from the combined data graph.

3. The system of claim 2, wherein the metadata includes a source of the first triple, so that after moving the metadata, the second triple is associated with the source of the first triple.

4. The system of claim 1, further comprising:

memory storing a plurality of reconciled source data graphs, each reconciled source data graph being associated with a different source, wherein the plurality of reconciled source data graphs are in the third identifier space, and wherein the reconciled version of the first source data graph and the reconciled version of the second source data graph are included in the plurality, and

wherein the memory further stores instructions that, when executed by the at least one processor, cause the computer system to;

determine a set of reconciled source data graphs identified by a graph view definition of a plurality of graph view definitions, the graph view definition identifying a set of the reconciled source data graphs, the set including the first source data graph and the reconciled version of the second source data graph, and

generate the combined data graph using the set of reconciled source data graphs.

5. The system of claim 4, wherein a new reconciled source data graph for a new source is added to the combined data graph by updating the graph view definition to include the new reconciled source data graph.

6. The system of claim 4, wherein the memory further stores instructions that, when executed by the at least one processor, cause the computer system to restrict access to the combined data graph in accordance with a restriction associated with the first source.

7. The system of claim 1, further comprising:

a source evidence file that maps the first identifier space to the third identifier space, the source evidence file mapping a particular entity in the first identifier space to a first global identifier in the third identifier space,

wherein the master evidence file maps the particular entity to a second global identifier in the third identifier space, and

wherein the memory further stores instructions that, when executed by the at least one processor, cause the computer system to;

determine the master evidence file does not map the particular entity to the first global identifier, and

responsive to the determining, updating the master evidence file to map the particular entity to the first global identifier, resulting in the particular entity mapping to both the first global identifier and the second global identifier in the master evidence file.

8. The system of claim 1, further comprising:

a first source evidence file that maps the first identifier space to a fourth identifier space, the first source evidence file mapping a first source identifier for a particular entity to a second source identifier in the fourth identifier space; and

a second source evidence file that maps the fourth identifier space to the third identifier space, the second source evidence file mapping the second source identifier to a global identifier in the third identifier space,

wherein the substituting includes;

determining that the first source evidence file fails to map to the third identifier space,

determining that the second source evidence file maps from the fourth identifier space to the third identifier space, and

replacing, using the first source evidence file and the second source evidence file, the first source identifier with the global identifier in the reconciled version of the first source data graph.

9. The system of claim 8, wherein the substituting further includes:

determining that the master evidence file fails to map the first source identifier to the global identifier; and

responsive to the determining, updating the master evidence file to map the first source identifier to the global identifier.

10. The system of claim 1, wherein the memory further stores instructions that, when executed by the at least one processor, cause the computer system to:

determine whether the first source data graph has changed; and

perform the generating when it is determined that the first source data graph has changed.

11. A computer-implemented method comprising:

generating, using at least one processor, a first reconciled data graph from a first source data graph using a master evidence file, the first reconciled data graph including a first set of triples, wherein the first reconciled data graph is in a global identifier space and the first source data graph is in a first local identifier space, the master evidence file mapping the first local identifier space to the global identifier space and a second local identifier space to the global identifier space;

generating, using the at least one processor, a second reconciled data graph from a second source data graph using the master evidence file, wherein the second reconciled data graph includes a second set of triples and the first source data graph differs from the second source data graph, wherein the second reconciled data graph is in the global identifier space and the second source data graph is in the second local identifier space, the first local identifier space differing from the second local identifier space;

generating a combined data graph from the first reconciled data graph and the second reconciled data graph on a periodic basis by;

appending the second set of triples to the first set of triples,

identifying a first triple in the first set of triples that matches a second triple in the second set of triples,

updating a source attribute for the second triple to reflect a value for the first source, and

deleting the first triple; and

making the combined data graph available for querying.

12. The method of claim 11, wherein generating the first reconciled data graph occurs in response to at least one update to the first source data graph.

13. The method of claim 12, wherein generating the first reconciled data graph results in a new version of the reconciled data graph and wherein a prior version of the first reconciled data graph is retained.

14. The method of claim 13, further comprising:

determining that the combined data graph is unstable; and

generating a new combined data graph from the prior version of the first reconciled data graph and the second reconciled data graph.

15. A method comprising:

generating a reconciled version of a first source data graph in a first identifier space by substituting identifiers in the first source data graph with identifiers in a third identifier space using a master evidence file, the first identifier space uniquely identifying items in the first source, and the third identifier space uniquely identifying items to a computer system, and the master evidence file mapping the first identifier space to the third identifier space and a second identifier space to the third identifier space;

generating a reconciled version of a second source data graph, the second source data graph being in the second identifier space and the reconciled version of the second source data graph being in the third identifier space, the second identifier space uniquely identifying items in the second source, wherein the first identifier space, the second identifier space, and the third identifier space differ from each other;

generating a combined data graph from the reconciled version of the first source data graph and the reconciled version of the second source data graph; and

making the combined data graph available for querying.

16. The method of claim 15, wherein generating the combined data graph includes:

determining that a first triple in the combined data graph is a duplicate of a second triple;

moving metadata about the first triple to the second triple; and

deleting the first triple from the combined data graph.

17. The method of claim 16, wherein the metadata includes a source of the first triple, so that after moving the metadata, the second triple is associated with the source of the first triple.

18. The method of claim 15, wherein the reconciled version of the first source data graph and the reconciled version of the second source data graph are included in a plurality of reconciled source data graphs, each reconciled source data graph being associated with a different source, wherein the plurality of reconciled source data graphs are in the third identifier space, and the method further comprises:

determining a set of reconciled source data graphs identified by a graph view definition of a plurality of graph view definitions, the graph view definition identifying a set of the reconciled source data graphs, the set including the first source data graph and the reconciled version of the second source data graph; and

generating the combined data graph using the set of reconciled source data graphs.

19. The method of claim 18, wherein a new reconciled source data graph for a new source is added to the combined data graph by updating the graph view definition to include the new reconciled source data graph.

20. The method of claim 18, further comprising restricting access to the combined data graph in accordance with a restriction associated with the first source.

21. The method of claim 15, wherein the substituting includes:

determining that a first source evidence file fails to map to the third identifier space, the first source evidence file mapping a first source identifier for a particular entity to a second source identifier in a fourth identifier space,

determining that a second source evidence file maps from the fourth identifier space to the third identifier space, the second source evidence file mapping the second source identifier to a global identifier in the third identifier space; and

replacing, using the first source evidence file and the second source evidence file, the first source identifier with the global identifier in the reconciled version of the first source data graph.