Information cataloging

• US 9,684,696 B2
• Filed: 06/22/2012
• Issued: 06/20/2017
• Est. Priority Date: 06/23/2011
• Status: Active Grant

• Current Assignee: FullContact, Inc.
• Original Assignee: FullContact, Inc.
• Inventors: Lynn, Daniel Kenton, Vargo, Brandon Wesley, Harriger, Kurt
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): Ye, Zi
• Application Number:
  US13/530,413
• Publication Number:
  US 20120331134A1
• Time in Patent Office: 1,824 Days
• Field of Search: 709224, 709223, 707766, 707999003, 707692
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]

Abstract

An information cataloging system disclosed herein provides a system and method for inferring relationships between various elements, such as e-mail address, phone number, etc., of various observations, such as business cards, observations obtained from the Internet, etc. The method comprises representing various elements, such as name, e-mail address, etc., using nodes, representing the relations between the various elements using edges connecting these nodes, computing a distance between two disparate nodes, wherein each of the two disparate nodes represent an element related to the entity. An implementation of the information cataloging system disclosed herein also provides a method of calculating noise and signal to noise ratio attached to various nodes and using such noise information in calculating confidence level of relationships between various elements.

Claims

1. A computer implemented method comprising:

detecting a plurality of observations about an entity from a plurality of sources, by a computer processor, the plurality of observations including one or more of various elements relating to the entity, the one or more of various elements including at least one of;

name, e-mail address, physical address, phone number, age, gender, employer, and social networking account;

representing the one or more of various elements from each of the plurality of observations about the entity using one or more nodes of a directed graph stored on a non-transitory computer readable media;

representing relations between the one or more nodes using edges connecting the one or more nodes in the directed graph;

computing, by the computer processor, a distance between two disparate nodes of the one or more nodes, each of the two disparate nodes representing an element related to the entity, wherein a shorter computed distance is associated to a higher confidence value that each of the two disparate nodes represent the entity;

inferring, by the computer processor, a relationship between the two disparate nodes based on the computed distance between the two disparate nodes;

assigning a noise level to the one or more of the nodes, wherein the noise level assigned to a node increasing the distance of an edge associated with that node and the noise level assigned to a node increasing if that node has multiple dissimilar associations to different nodes;

calculating a signal to noise ratio (SNR) of an edge based on noise levels of the nodes attached to that edge;

determining validity of a relationship between the two disparate nodes if the SNR of the edge connecting the two disparate nodes is above a threshold;

automatically generating and outputting an identity for the entity, by the computer processor, based on the one or more of various elements and the relationship inferred between the two disparate nodes, the identity including a listing of one or more of the various elements relating to the entity and reflecting the relationship inferred between the two disparate nodes; and

cataloging the identity for the entity in an information cataloging system by storing the identity in a database, the information cataloging system configured to respond to a user query based on the cataloged identity.

2. The method of claim 1, wherein computing the distance between two disparate nodes further comprises:

computing a first distance between one of the two disparate nodes to a third node;

computing a second distance between the other of the two disparate nodes to the third node; and

computing the distance between the two disparate nodes using a combination of the first distance and the second distance.

3. The method of claim 2, wherein computing the distance between the two disparate nodes further comprises computing the distance between the two disparate nodes as a ratio of the product of the first distance and the second distance to the sum of the first distance and the second distance.

4. The method of claim 2, further comprising assigning a confidence level to one or more of the nodes, wherein the confidence level is determined based on a source of the observation containing the one or more of the nodes.

5. The method of claim 4, wherein computing the distance between the two disparate nodes further comprises computing the distance between the two disparate nodes using the confidence level assigned to each of the two disparate nodes.

6. The method of claim 4, wherein the confidence level assigned to a particular node varies with age of the particular node.

7. The method of claim 4, wherein the confidence level assigned to a particular node varies based on the frequency of observation generating the particular node.

8. The method of claim 1, further comprising comparing at least two of the one or more nodes with each other and removing at least one of the two nodes if similarity between the two nodes is above a similarity threshold.

9. The method of claim 1, wherein inferring the relationship further comprises inferring higher order relationship between the two disparate nodes.

10. The method of claim 1, wherein inferring the relationship further comprises

comparing the computed distance to a threshold;

and

inferring the relationship if the computed distance is higher than the threshold.

11. The method of claim 1, wherein the threshold is 0.7.

12. The method of claim 1, further comprising propagating the noise attached to first node to a second node connected indirectly to the first node.

13. The method of claim 1, wherein in calculating the SNR of an edge, the signal levels of the nodes are added inversely and the noise levels of the nodes are added linearly.

14. The method of claim 1, wherein the elements of the observations (1) are related to one of the entity and (2) represent metadata about the entity.

15. The computer implemented method of claim 1 wherein the method further comprises automatically updating one or more of the plurality of sources with one or more elements relating to the entity.

16. A non-transitory computer-readable storage medium embodied with computer-executable instructions for executing on one or more processors and circuits of a device a process comprising:

detecting a plurality of observations about an entity from a plurality of sources, the plurality of observations including one or more of various elements relating to the entity, the one or more of various elements including at least one of;

name, e-mail address, physical address, phone number, age, gender, employer, and social networking account;

representing the one or more of various elements from each of the plurality of observations about the entity using one or more nodes of a directed graph;

representing relations between the one or more nodes using edges connecting the one or more nodes in the directed graph;

computing a distance between two disparate nodes of the one or more nodes, each of the two disparate nodes representing an element related to the entity, wherein a shorter computed distance is associated to a higher confidence value that each of the two disparate nodes represent the entity;

inferring a relationship between the two disparate nodes based on the computed distance between the two disparate nodes;

assigning a noise level to each of the two disparate nodes, wherein the noise level assigned to a node increasing the distance of an edge associated with that node and the noise level assigned to a node increasing if that node has multiple dissimilar associations to different nodes;

calculating a signal to noise ratio (SNR) of an edge based on noise levels of the nodes attached to that edge;

determining validity of a relationship between the two disparate nodes if the SNR of the edge connecting the two disparate nodes is above a threshold;

automatically generating and outputting an identity for the entity based on the one or more of various elements and the relationship inferred between the two disparate nodes, the identity including a listing of one or more of the various elements relating to the entity and reflecting the relationship inferred between the two disparate nodes; and

cataloging the identity for the entity in an information cataloging system by storing the identity in a database, the information cataloging system configured to respond to a user query based on the cataloged identity.

17. The non-transitory computer-readable storage medium of claim 16, wherein the process further comprises:

computing a first distance between one of the two disparate nodes to a third node;

computing a second distance between the other of the two disparate nodes to the third node; and

computing the distance between the two disparate nodes as a ratio of the product of the first distance and the second distance to the sum of the first distance and the second distance.

18. The non-transitory computer-readable storage medium of claim 16, wherein the process further comprises comparing at least two of the various nodes with each other and collapsing at least one of the two nodes into the other of the two nodes if the similarity between the two nodes is above a similarity threshold.

19. The non-transitory computer-readable storage medium of claim 16, wherein inferring a relationship between the two disparate nodes further comprises inferring a higher order relationship between the two disparate nodes based on relationship of each of the two disparate nodes to a third node.

20. The non-transitory computer-readable storage medium of claim 16, wherein the process further comprises computing the distance between the two disparate nodes further comprises computing the distance between the two disparate nodes using confidence levels assigned to each of the two disparate nodes.

21. The non-transitory computer-readable storage medium of claim 20, wherein the confidence level assigned to a particular node varies with age of the particular node and based on the frequency of observation generating the particular node.

22. The non-transitory computer-readable storage medium of claim 16, wherein the process further comprises propagating the noise attached to first node to a second node connected to the first node.

23. The non-transitory computer-readable storage medium of claim 16 having computer-executable instructions, further comprising:

automatically updating one or more of the plurality of sources with one or more elements relating to the entity.

24. A system, comprising:

a processor and a non-transitory computer readable memory, wherein the non-transitory computer readable memory comprises instructions for executing on the processor, the instructions including;

a graph generation module configured to represent one or more of various elements from each of a plurality of observations about an entity, the plurality of observations including one or more of various elements relating to the entity, using one or more nodes of a directed graph in the memory and to represent relations between the one or more nodes using edges stored in the memory, the edges connecting the one or more nodes in the directed graph, the one or more of various elements including at least one of;

name, e-mail address, physical address, phone number, age, gender, employer, and social networking account;

a graph traversal module configured to compute a distance between two disparate nodes of the one or more nodes, each of the two disparate nodes representing an element related to the entity and the distance between the two disparate nodes indicating a likelihood that the two disparate nodes belong to the entity;

an inference module configured to;

infer a relationship between the two disparate nodes based on the computed distance between the two disparate nodes;

assign a noise level to one of the two disparate nodes if the one of the two disparate nodes has multiple dissimilar associations to different nodes of the same type;

propagating the noise level to an edge connecting the two disparate nodes;

calculate a signal to noise ratio (SNR) of the edge connecting the two disparate nodes, the SNR being based on the noise level of the two disparate nodes;

determine a validity of the relationship between the two disparate nodes if the SNR of the edge connecting the two disparate nodes is above a threshold;

wherein the graph traversal module is further configured to automatically generate and output an identity for the entity based on the one or more of various elements and the relationship inferred between the two disparate nodes, the identity including a listing of one or more of the various elements relating to the entity and reflecting the relationship inferred between the two disparate nodes; and

a remote procedure call module configured to catalog the identity for the entity in an information cataloging system by storing the identity in a database, the information cataloging system configured to respond to a user query based on the cataloged identity.