Matching co-referring entities from serialized data for schema inference

Patent metadata

Field	Value
Publication number	US-9977817-B2
Application number	US-201414518361-A
Country	US
Kind code	B2
Filing date	Oct 20, 2014
Priority date	Oct 20, 2014
Publication date	May 22, 2018
Grant date	May 22, 2018

Abstract

A system and method provide for identifying coreference from serialized data coming from different services. The method includes generating a tree structure from serialized data. The serialized data includes responses to queries from the different services. The responses each identify a hierarchical relationship between a respective set of objects. Nodes of the tree structure each have a name corresponding to a respective one of the objects. The tree structure is traversed in a breadth first manner and, for each node in the tree structure, a respective pairwise similarity is computed with each of the other nodes of the tree structure. The computed pairwise similarity is compared with a threshold to identify co-referring nodes that refer to a same entity. The threshold is a function of a depth of the node in the tree structure.

First claim

What is claimed is:

1. A method for identifying coreference from serialized data comprising:
generating a tree structure from serialized data, the serialized data comprising responses to queries from different services, the responses each identifying a hierarchical relationship between a respective set of objects, nodes of the tree structure each having a name corresponding to a respective one of the objects;
traversing the tree structure in a breadth first manner and for each node in the tree structure, computing a respective pairwise similarity with other nodes of the tree structure;
comparing the computed pairwise similarity with a threshold to identify co-referring nodes that refer to a same entity, the threshold being a function of a depth of the node in the tree structure;
merging two nodes identified as being co-referring nodes, the merging including identifying all of the children of the two nodes as having both of the two nodes as their parents;
generating a directed acyclic graph which includes the merged nodes; and
outputting information based on the identified co-referring nodes, the information comprising the directed acyclic graph or information based thereon,
wherein at least one of the generating of the tree structure, computing a respective pairwise similarity, and identifying co-referring nodes is performed with a processor.

2. The method of claim 1 , wherein the computing of the pairwise similarity comprises computing a first similarity based on a similarity of the two nodes being compared and computing a second similarity based on a similarity of children of the two nodes being compared and aggregating the first and second similarities.

3. The method of claim 2 , wherein the computing of the first similarity is also based on parents of the two nodes being compared.

4. The method of claim 2 , wherein the computing of the second similarity comprises identifying a number of overlapping children of the first and second nodes.

5. The method of claim 4 , wherein the second similarity is a function of:

sim
2

⁡

(

n
,

n
′

)

=



n
.
children

⋂

n
′

.
children



min
(



n
.
children



,



n
′

.
children



where n represents the first node and n′ represents the second node.

6. The method of claim 2 , wherein the aggregating comprises multiplying the first and second similarities.

7. The method of claim 6 , wherein the threshold is a function of

m
+

(

M
-
m

)

⁢

1
-

h
H

,

where m and M are predefined constant values, h is a depth of the node and H is a maximum depth of the tree structure.

8. The method of claim 1 , wherein the threshold is a concave decreasing function of the depth.

9. The method of claim 1 , further comprising merging two nodes identified as being co-referring objects, the merging including identifying all of the children of the two nodes as having both of the two nodes as their parents.

10. The method of claim 9 , comprising generating a directed acyclic graph which includes the merged nodes.

11. The method of claim 1 wherein the serialization format of the serialized data is JSON.

12. The method of claim 1 , wherein the generating of the tree structure from serialized data comprises merging objects of a list into one node which has as its name the key-value of its parent key.

13. The method of claim 1 , wherein the services are services of a same organization that use at least one of:
different names for the same object, and
a same name for different objects.

14. The method of claim 1 , wherein the serialized data comprises responses to queries of a database, the method further comprising:
enriching a database with information on the identified co-referring nodes.

15. A method for identifying coreference from serialized data comprising:
generating a tree structure from serialized data, the serialized data comprising responses to database queries from different services, the responses each identifying a hierarchical relationship between a respective set of objects, nodes of the tree structure each having a name corresponding to a respective one of the objects;
traversing the tree structure in a breadth first manner and for each node in the tree structure, computing a respective pairwise similarity with other nodes of the tree structure, the computing of the pairwise similarity comprising:
computing a first similarity based on a similarity of the two nodes being compared, and
computing a second similarity based on a similarity of children of the two nodes being compared and aggregating the first and second similarities, wherein at least one of:
a) the computing of the first similarity is also based on parents of the two nodes being compared and comprises computing a similarity based on a maximal value of the name of the second node and a combination of the name of the second node with its parent's name, and
b) the computing of the second similarity comprises identifying a number of overlapping children of the first and second nodes, the second similarity being a function of:

sim
2

⁡

(

n
,

n
′

Assignees

• Conduent Business Services Llc

Inventors

• Gallé Matthias
• Lagos Nikolaos

Classifications

• G06F16/25 Primary

  Integrating or interfacing systems involving database management systems · CPC title

• G06F17/30557 Primary

  Physics · mapped topic