Method and system to compare data objects

• US 7,440,955 B2
• Filed: 04/25/2005
• Issued: 10/21/2008
• Est. Priority Date: 01/14/2005
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: IM2, Inc. (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Inventors: Pardasani, Dhiraj, Khandelwal, Shashikant, Padmanabhan, Ranjit, Meyer, Alex, Kakade, Vinay
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): NGUYEN, THU N
• Application Number:
  US11/113,883
• Publication Number:
  US 20060161560A1
• Time in Patent Office: 1,275 Days
• Field of Search: 707/100, 715/700, 715/866
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

The invention provides a method and system to compare data objects. Each data object is converted into a directed acyclic graph forest, which comprises one or more directed acyclic graphs. The directed acyclic graph forests corresponding to data objects are then compared to calculate a similarity score between the data objects. The similarity score is then used as a measure to determine the extent of similarity between the data objects.

Claims

1. A method for comparing a first data object with a second data object, the first data object comprising first unstructured data, the first unstructured data comprising one or more first sets of ontology-based attributes pertaining to a domain knowledge model, the second data object comprising second unstructured data, the second unstructured data comprising one or more second sets of ontology-based attributes pertaining to the domain knowledge model, the domain knowledge model comprising one or more data acyclic graphs representing the one or more first sets of ontology-based attributes and the one or more second sets of ontology-based attributes, the method comprising the steps of:

a. converting the first data object into a first directed acyclic graph forest, the first directed acyclic graph forest comprising a first set of one or more directed acyclic graphs, wherein the first set of one or more data acyclic graphs are constructed from the one or more directed acyclic graphs of the domain knowledge model representing the one or more first set of ontology-based attributes of the first data object;

b. converting the second data object into a second directed acyclic graph forest, the second directed acyclic graph forest comprising a second set of one or more directed acyclic graphs, wherein the second set of one or more data acyclic graphs are constructed from the one or more directed acyclic graphs of the domain knowledge model representing the one or more second set of ontology-based attributes of the second data object;

c. determining a graph-based similarity score between each directed acyclic graph of the first set of one or more directed acyclic graphs and a corresponding directed acyclic graph of the second set of one or more directed acyclic graphs, wherein the graph based similarity score is determined by calculating a cosine distance between vectors defined by the each directed acyclic graph of the first set of one or more directed acyclic graphs and the corresponding directed acyclic graph of the second set of one or more directed acyciic graphs; and

d. determining a forest-based similarity score between the first directed acyclic graph forest of the first data object and the second directed acyclic graph forest of the second data object, wherein the forest-based similarity score is calculated as a function of the graph-based similarity score between each directed acyclic graph of the first set of one or more directed acyclic graphs and a corresponding directed acyclic graph of the second set of one or more directed acyclic graphs.

2. The method of claim 1, wherein the first set of one or more directed acyclic graphs and the second set of one or more directed acyclic graphs are constructed by the steps of:

a. assigning weights to each of the one or more first set of identified nodes of the one or more directed acyclic graphs of the domain knowledge model corresponding to the one or more first set of ontology based attributes, wherein the weights being assigned based on presence of the first unstructured data corresponding to the one or more first set of ontology-based attributes in the first data object;

b. assigning weights to each of the one or more second set of identified nodes of the one or more directed acyclic graphs of the domain knowledge model corresponding to the one or more second set of ontology based attributes, wherein the weights being assigned based on presence of the second unstructured data corresponding to the one or more second set of ontology-based attributes in the second data object;

c. propagating the weights assigned to each of the one or more first set of identified nodes to the corresponding ancestor nodes and descendant nodes of each of the one or more directed acyclic graphs of the domain knowledge model to construct the first set of one or more directed acyclic graphs representing the one or more first set of ontology-based attributes, wherein the one or more first set of identified nodes with ancestor nodes and descendant nodes are present in the first set of one or more directed acyclic graphs representing the one or more first set of ontology-based attributes; and

d. propagating the weights assigned to each of the one or more second set of identified nodes to the corresponding ancestor nodes and descendant nodes of each of the one or more directed acyclic graphs of the domain knowledge model to from the second set of one or more directed acyclic graphs representing the one or more second set of ontology-based attributes, wherein the one or more second set of identified nodes with ancestor nodes and descendant nodes are present in the second set of one or more directed acyclic graphs representing the one or more second set of ontology-based attributes.

3. The method of claim 2, wherein the step of propagating the weights further comprises the step of:

a. normalizing the weights of each of the one or more identified first set of nodes of the first set of one or more directed acyclic graphs and one or more second set of identified nodes of the second set of one or more directed acyclic graphs, wherein the normalization is based on the weights assigned to the corresponding ancestor nodes and the corresponding descendant nodes of the one or more first set of identified nodes and the one or more second set of identified nodes.

4. The method of claim 1, wherein first unstructured data in the first data object is at least one of a text document, an XML document, a web page and a natural language query.

5. The method of claim 1, wherein the second unstructured data in the second data object is at least one of a text document, an XML document, a web page and a natural language query.

11. The method of claim 1, wherein the step of converting the first data object to the first data acyclic graph forest and converting the second data object to the second data acyclic graph forest further comprises the steps of:

a. recognizing variants for each of the one or more first set of ontology-based attributes of the first unstructured data in the one or more directed acyclic graphs of the domain knowledge model, the variants comprising at least one of synonyms for at least one of the one or more first set of ontology-based attributes and alternative names for the at least one of the first set of one or more ontology-based attributes;

b. recognizing variants for each of the one or more second set of ontology-based attributes of the second unstructured data in the one or more directed acyclic graphs of the domain knowledge model, the variants comprising at least one of synonyms for at least one of the one or more second set ontology-based attributes and alternative names for the at least one of the one or more second set of ontology-based attributes;

c. identifying one or more first set of nodes corresponding to each of the one or more first set of ontology-based attributes and variants of each of the one or more first set of ontology-based attributes in the one or more directed acyclic graphs of the domain knowledge model; and

d. identifying one or more second set of nodes corresponding to each of the one or more second set of ontology-based attributes and variants of each of the one or more second set of ontology-based attributes in the one or more directed acyclic graphs of the domain knowledge model.

6. A system for comparing a first data object with a second data object, the first data object comprising first unstructured data, the first unstructured data comprising one or more first sets of ontology-based attributes pertaining to a domain knowledge model, the second data object comprising second unstructured data, the second unstructured data comprising one or more second sets of ontology-based attributes pertaining to the domain knowledge model, the domain knowledge model comprising one or more data acyclic graphs representing the one or more first sets of ontology-based attributes and the one or more second sets of ontology-based attributes, the system comprising:

a processor;

a. a data converter to convert the first data object into a first directed acyclic graph forest and the second data object into a second directed acyclic graph forest, the first directed acyclic graph forest comprising a first set of one or more directed acyclic graphs wherein the first set of one or more data acyclic graphs are constructed from the one or more directed acyclic graphs of the domain knowledge model representing the one or more first set of ontology-based attributes of the first data object and the second directed acyclic graph forest comprising a second set of one or more directed acyclic graphs wherein the second set of one or more data acyclic graphs are constructed from the one or more directed acyclic graphs of the domain knowledge model representing the one or more second set of ontology-based attributes of the second data object the first set of one or more directed acyclic graphs being formed based on one or more first set of one or more ontology based attributes of the first data object and

b. a similarity-calculator to determine the extent of similarity between the first directed acyclic graph forest and the second directed acyclic graph forest, the similarity calculator comprising;

a graph-based similarity-score calculator to determine a graph-based similarity score between each directed acyclic graph of the first set of one or more directed acyclic graphs and a corresponding directed acyclic graph of the second set of one or more directed acyclic graphs, wherein the graph based similarity score is determined by calculating a cosine distance between vectors defined by the each directed acyclic graph of the first set of one or more directed acyclic graphs and the corresponding directed acyclic graph of the second set of one or more directed acyclic graphs; and

a forest-based similarity-score calculator to determine a forest-based similarity score between the first directed acyclic graph forest of the first data object and the second directed acyclic graph forest of the second data object, wherein the forest-based similarity score is calculated as a function of the graph-based similarity score between each directed acyclic graph of the first set of one or more directed acyclic graphs and a corresponding directed acyclic graph of the second set of one or more directed acyclic graphs.

7. The system of claim 6, further comprising:

a. a weight assigning module for assigning weights to each one or more first set of identified nodes of the one or more directed acyclic graphs of the domain knowledge model corresponding to the one or more first sets of ontology based attributes and each one or more second sets of identified nodes of the one or more directed acyclic graphs of the domain knowledge model corresponding to the one or more second set of ontology based attributes and for propagating weights assigned to the each one or more first set of identified nodes to corresponding ancestor nodes and descendant nodes of each of the one or more directed acyclic graphs of the domain knowledge model to construct the first set of one or more directed acyclic graphs representing the one or more first set of ontology-based attributes, wherein the one or more first set of identified nodes with ancestor nodes and descendant nodes are present in the first set of one or more directed acyclic graphs representing the one or more first set of ontology-based attributes and to the each one or more second set of identified nodes to the corresponding ancestor nodes and descendant nodes of each of the one or more directed acyclic graphs of the domain knowledge model to construct the second set of one or more directed acyclic graphs representing the one or more second set of ontology-based attributes, wherein the one or more second set of identified nodes with ancestor nodes and descendant nodes are present in the second set of one or more directed acyclic graphs representing the one or more second set of ontology-based attributes.

8. A computer program product for use with a computer, the computer program product comprising a computer usable medium having a computer program code embodied therein for comparing a first data object with a second data object, the first data object comprising first unstructured data, the first unstructured data comprising one or more first set of ontology-based attributes pertaining to a domain knowledge model, the second data object comprising second unstructured data, the second unstructured data comprising one or more second set of ontology-based attributes pertaining to the domain knowledge model, the domain knowledge model comprising one or more data acyclic graphs representing one or more first set of ontology-based attributes and one or more second set of ontology-based attributes, the computer code performing the steps of:

a. converting the first data object into a first directed acyclic graph forest, the first directed acyclic graph forest comprising a first set of one or more directed acyclic graphs, wherein the first set of one or more data acyclic graphs are constructed from the one or more directed acyclic graphs of the domain knowledge model representing the one or more first set of ontology-based attributes of the first data object;

b. converting the second data object into a second directed acyclic graph forest, the second directed acyclic graph forest comprising a second set of one or more directed acyclic graphs, wherein the second set of one or more data acyclic graphs are constructed from the one or more directed acyclic graphs of the domain knowledge model representing the one or more second set of ontology-based attributes of the second data object;

c. determining a graph-based similarity score between each directed acyclic graph of the first set of one or more directed acyclic graphs and a corresponding directed acyclic graph of the second set of one or more directed acyclic graphs, wherein the graph based similarity score is determined by calculating cosine distance between vectors defined by the each directed acyclic graph of the first set of one or more directed acyclic graphs and the corresponding directed acyclic graph of the second set of one or more directed acyclic graphs; and

d. determining a forest-based similarity score between the first directed acyclic graph forest of the first data object and the second directed acyclic graph forest of the second data object, wherein the forest-based similarity score is calculated as a function of the graph-based similarity score between each directed acyclic graph of the first set of one or more directed acyclic graphs and a corresponding directed acyclic graph of the second set of one or more directed acyclic graphs.

9. The computer program product of claim 8, wherein the first set of one or more directed acyclic graphs and the second set of one or more directed acyclic graphs are constructed by a computer code performing the steps of:

a. assigning weights to each of the one or more first set of identified nodes of the one or more directed acyclic graphs of the domain knowledge model corresponding to the one or more first set of ontology based attributes, wherein the weights being assigned based on presence of the first unstructured data corresponding to the one or more first set of ontology-based attributes in the first data object;

b. assigning weights to each of the one or more second set of identified nodes of the one or more directed acyciic graphs of the domain knowledge model corresponding to the one or more second set of ontology based attributes, wherein the weights being assigned based on presence of the second unstructured data corresponding to the one or more second set of ontology-based attributes in the second data object;

c. propagating the weights assigned to each of the one or more first set of identified nodes to corresponding ancestor nodes and corresponding descendant nodes of each of the one or more directed acyclic graphs of the domain knowledge model to construct the first set of one or more directed acyclic graphs representing the one or more first set of ontology-based attributes, wherein the one or more first set of identified nodes with the corresponding ancestor nodes and the corresponding descendant nodes are present in the first set of one or more directed acyclic graphs representing the one or more first set of ontology-based attributes ; and

d. propagating the weights assigned to each of the one or more second set of identified nodes to corresponding ancestor nodes and corresponding descendant nodes of each of the one or more directed acyclic graphs of the domain knowledge model to from the second set of one or more directed acyclic graphs representing the one or more second set of ontology-based attributes, wherein the one or more second set of identified nodes with the corresponding ancestor nodes and the corresponding descendant nodes are present in the second set of one or more directed acyclic graphs representing the one or more second set of ontology-based attributes.

10. The computer program product of claim 9, wherein propagating the weights further comprises computer code to perform the step of:

a. normalizing the weights of each of the one or more identified first set of nodes of the first set of one or more directed acyclic graphs and one or more second set of identified nodes of the second set of one or more directed acyclic graphs, wherein the normalization is based on the weights assigned to the corresponding ancestor nodes and the corresponding descendant nodes of the one or more first set of identified nodes and the one or more second set of identified nodes.

12. The computer program product of claim 8, wherein converting the first data object to the first data acyclic graph forest and converting the second data object to the second data acyclic graph forest further comprises the steps of:

a. recognizing variants for each of the one or more first set of ontology-based attributes of the first unstructured data in the one or more directed acyclic graphs of the domain knowledge model, the variants comprising at least one of synonyms for at least one of the one or more first set of ontology-based attributes and alternative names for the at least one of the first set of one or more ontology-based attributes;

b. recognizing variants for each of the one or more second set of ontology-based attributes of the second unstructured data in the one or more directed acyclic graphs of the domain knowledge model, the variants comprising at least one of synonyms for at least one of the one or more second set ontology-based attributes and alternative names for the at least one of the one or more second set of ontology-based attributes;

c. identifying one or more first set of nodes corresponding to each of the one or more first set of ontology-based attributes and variants of each of the one or more first set of ontology-based attributes in the one or more directed acyclic graphs of the domain knowledge model; and

d. identifying one or more second set of nodes corresponding to each of the one or more second set of ontology-based attributes and variants of each of the one or more second set of ontology-based attributes in the one or more directed acyclic graphs of the domain knowledge model.