Data clustering based on variant token networks

• US 9,037,589 B2
• Filed: 11/15/2012
• Issued: 05/19/2015
• Est. Priority Date: 11/15/2011
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Inventors: Anderson, Arlen
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Allen, Nicholas
• Application Number:
  US13/678,038
• Publication Number:
  US 20130124524A1
• Time in Patent Office: 915 Days
• Field of Search: None
• US Class Current: 707/737
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/3338 Query expansion

Abstract

Received data records, each including one or more values in one or more fields, are processed to identify one or more data clusters. The processing includes: identifying tokens that each include at least one value or fragment of a value in a field or a combination of fields; generating a network representing the identified tokens, with nodes of the network representing tokens and edges of the network each representing a variant relationship between tokens; and generating a graphical representation of the network with different subsets of nodes distinguished based at least in part on values associated with nodes, where a value associated with a particular node quantifies a count of a number of instances of the token represented by that particular node appearing within the received data records.

Claims

1. A method, including:

receiving data records, the received data records each including one or more values in one or more fields; and

processing the received data records to identify one or more data clusters of two or more data records, where the data clusters are identified based on candidate data records that are identified based on a network representing identified tokens, the processing including;

identifying tokens that each include at least one value or fragment of a value in a field or a combination of fields of the received data records;

generating the network representing the identified tokens, with nodes of the network representing individual tokens and edges of the network each representing a variant relationship between tokens;

identifying, for each received data record to be associated with a data cluster, a corresponding set of candidate data records, such that candidate data records that are in the same set each include one or more tokens from the same group of tokens represented by a subset of connected nodes in the generated network; and

for at least one candidate data record in the set of candidate data records corresponding to a received data record, determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs.

2. The method of claim 1, wherein two tokens have a variant relationship if a distance between the tokens is below a threshold.

3. The method of claim 2, wherein the distance is measured based on sequences of shared characters.

4. The method of claim 1, further including identifying at least one node associated with a value that is larger than the mean of values associated with the other nodes in the first set by more than a threshold.

5. The method of claim 4, further including determining any two of the identified nodes that are directly connected to each other by an edge.

6. The method of claim 1, further including receiving input from a user or a predetermined rule applied to the network to modify the network by adding an edge between two nodes or removing an edge between two nodes.

7. The method of claim 6, further including displaying in a user interface a visual representation of the network, and visually indicating the values associated with the nodes.

8. The method of claim 7, further including receiving the input through the user interface.

9. The method of claim 1, wherein the processing further includes generating a graphical representation of the network in which different subsets of nodes are distinguished, based at least in part on values associated with nodes, where a value associated with a particular node quantifies a count of a number of instances of the token represented by that particular node appearing within the received data records.

10. The method of claim 9, wherein determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs includes retrieving at least one representative data record of the candidate data cluster to which the candidate data record belongs, and comparing the received data record to the representative data record.

11. The method of claim 10, wherein at least a first subset includes at least one node associated with a token that is a representative for tokens represented by other nodes in the first subset.

12. The method of claim 11, wherein identifying a data cluster to associate with a first received data record includes replacing at least one token in the first received data record with its representative token.

13. The method of claim 9, wherein nodes that are associated with a value greater than a threshold are graphically distinguished from nodes that do not have a value greater than the threshold.

14. The method of claim 9, wherein at least one subset includes a first node and nodes obtained by traversing edges that connect to nodes associated with equal or lower values than the value associated with the first node.

15. The method of claim 1, wherein determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs includes retrieving at least one representative data record of the candidate data cluster to which the candidate data record belongs, and comparing the received data record to the representative data record.

16. A computer program stored on a non-transitory computer-readable medium, the computer program including instructions for causing a computing system to:

receive data records, the received data records each including one or more values in one or more fields; and

process the received data records to identify one or more data clusters of two or more data records, where the data clusters are identified based on candidate data records that are identified based on a network representing identified tokens, the processing including;

identifying tokens that each include at least one value or fragment of a value in a field or a combination of fields of the received data records;

generating the network representing the identified tokens, with nodes of the network representing individual tokens and edges of the network each representing a variant relationship between tokens;

identifying, for each received data record to be associated with a data cluster, a corresponding set of candidate data records, such that candidate data records that are in the same set each include one or more tokens from the same group of tokens represented by a subset of connected nodes in the generated network; and

for at least one candidate data record in the set of candidate data records corresponding to a received data record, determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs.

19. The computer program of claim 16, wherein the processing further includes generating a graphical representation of the network in which different subsets of nodes are distinguished, based at least in part on values associated with nodes, where a value associated with a particular node quantifies a count of a number of instances of the token represented by that particular node appearing within the received data records.

20. The computer program of claim 19, wherein determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs includes retrieving at least one representative data record of the candidate data cluster to which the candidate data record belongs, and comparing the received data record to the representative data record.

21. The computer program of claim 20, wherein at least a first subset includes at least one node associated with a token that is a representative for tokens represented by other nodes in the first subset.

22. The computer program of claim 21, wherein identifying a data cluster to associate with a first received data record includes replacing at least one token in the first received data record with its representative token.

23. The computer program of claim 20, wherein nodes that are associated with a value greater than a threshold are graphically distinguished from nodes that do not have a value greater than the threshold.

24. The computer program of claim 20, wherein at least one subset includes a first node and nodes obtained by traversing edges that connect to nodes associated with equal or lower values than the value associated with the first node.

25. The computer program of claim 16, wherein determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs includes retrieving at least one representative data record of the candidate data cluster to which the candidate data record belongs, and comparing the received data record to the representative data record.

26. The computer program of claim 16, wherein two tokens have a variant relationship if a distance between the tokens is below a threshold.

27. The computer program of claim 26, wherein the distance is measured based on sequences of shared characters.

28. The computer program of claim 16, the processing further including identifying at least one node associated with a value that is larger than the mean of values associated with the other nodes in the first set by more than a threshold.

29. The computer program of claim 28, the processing further including determining any two of the identified nodes that are directly connected to each other by an edge.

30. The computer program of claim 16, further including instructions for causing the computing system to receive input from a user or a predetermined rule applied to the network to modify the network by adding an edge between two nodes or removing an edge between two nodes.

31. The computer program of claim 30, further including instructions for causing the computing system to display in a user interface a visual representation of the network, and visually indicating the values associated with the nodes.

32. The computer program of claim 31, further including instructions for causing the computing system to receive the input through the user interface.

17. A computing system, including:

an input device or port configured to receive data records, the received data records each including one or more values in one or more fields; and

at least one processor configured to process the received data records to identify one or more data clusters of two or more data records, where the data clusters are identified based on candidate data records that are identified based on a network representing identified tokens, the processing including;

identifying tokens that each include at least one value or fragment of a value in a field or a combination of fields of the received data records;

generating the network representing the identified tokens, with nodes of the network representing individual tokens and edges of the network each representing a variant relationship between tokens;

identifying, for each received data record to be associated with a data cluster, a corresponding set of candidate data records, such that candidate data records that are in the same set each include one or more tokens from the same group of tokens represented by a subset of connected nodes in the generated network; and

for at least one candidate data record in the set of candidate data records corresponding to a received data record, determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs.

33. The computing system of claim 17, wherein the processing further includes generating a graphical representation of the network in which different subsets of nodes are distinguished, based at least in part on values associated with nodes, where a value associated with a particular node quantifies a count of a number of instances of the token represented by that particular node appearing within the received data records.

34. The computing system of claim 33, wherein determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs includes retrieving at least one representative data record of the candidate data cluster to which the candidate data record belongs, and comparing the received data record to the representative data record.

35. The computing system of claim 34, wherein at least a first subset includes at least one node associated with a token that is a representative for tokens represented by other nodes in the first subset.

36. The computing system of claim 35, wherein identifying a data cluster to associate with a first received data record includes replacing at least one token in the first received data record with its representative token.

37. The computing system of claim 34, wherein nodes that are associated with a value greater than a threshold are graphically distinguished from nodes that do not have a value greater than the threshold.

38. The computing system of claim 34, wherein at least one subset includes a first node and nodes obtained by traversing edges that connect to nodes associated with equal or lower values than the value associated with the first node.

39. The computing system of claim 17, wherein determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs includes retrieving at least one representative data record of the candidate data cluster to which the candidate data record belongs, and comparing the received data record to the representative data record.

40. The computing system of claim 17, wherein two tokens have a variant relationship if a distance between the tokens is below a threshold.

41. The computing system of claim 40, wherein the distance is measured based on sequences of shared characters.

42. The computing system of claim 17, the processing further including identifying at least one node associated with a value that is larger than the mean of values associated with the other nodes in the first set by more than a threshold.

43. The computing system of claim 42, the processing further including determining any two of the identified nodes that are directly connected to each other by an edge.

44. The computing system of claim 17, further including a user interface for receiving input from a user or a predetermined rule applied to the network to modify the network by adding an edge between two nodes or removing an edge between two nodes.

45. The computing system of claim 44, wherein the user interface displays a visual representation of the network, and visually indicating the values associated with the nodes.

46. The computing system of claim 45, wherein the user interface receives the input.

18. A computing system, including:

means for receiving data records, the received data records each including one or more values in one or more fields; and

means for processing the received data records to identify one or more data clusters of two or more data records, where the data clusters are identified based on candidate data records that are identified based on a network representing identified tokens, the processing including;

identifying tokens that each include at least one value or fragment of a value in a field or a combination of fields of the received data records;

generating the network representing the identified tokens, with nodes of the network representing individual tokens and edges of the network each representing a variant relationship between tokens;

identifying, for each received data record to be associated with a data cluster, a corresponding set of candidate data records, such that candidate data records that are in the same set each include one or more tokens from the same group of tokens represented by a subset of connected nodes in the generated network; and

for at least one candidate data record in the set of candidate data records corresponding to a received data record, determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs.

47. The computing system of claim 18, wherein the processing further includes generating a graphical representation of the network in which different subsets of nodes are distinguished, based at least in part on values associated with nodes, where a value associated with a particular node quantifies a count of a number of instances of the token represented by that particular node appearing within the received data records.

48. The computing system of claim 47, wherein determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs includes retrieving at least one representative data record of the candidate data cluster to which the candidate data record belongs, and comparing the received data record to the representative data record.

49. The computing system of claim 48, wherein at least a first subset includes at least one node associated with a token that is a representative for tokens represented by other nodes in the first subset.

50. The computing system of claim 49, wherein identifying a data cluster to associate with a first received data record includes replacing at least one token in the first received data record with its representative token.

51. The computing system of claim 48, wherein nodes that are associated with a value greater than a threshold are graphically distinguished from nodes that do not have a value greater than the threshold.

52. The computing system of claim 48, wherein at least one subset includes a first node and nodes obtained by traversing edges that connect to nodes associated with equal or lower values than the value associated with the first node.

53. The computing system of claim 18, wherein determining whether or not the received data record satisfies a cluster association criterion for a candidate data cluster to which the candidate data record belongs includes retrieving at least one representative data record of the candidate data cluster to which the candidate data record belongs, and comparing the received data record to the representative data record.

54. The computing system of claim 18, wherein two tokens have a variant relationship if a distance between the tokens is below a threshold.

55. The computing system of claim 54, wherein the distance is measured based on sequences of shared characters.

56. The computing system of claim 18, the processing further including identifying at least one node associated with a value that is larger than the mean of values associated with the other nodes in the first set by more than a threshold.

57. The computing system of claim 56, the processing further including determining any two of the identified nodes that are directly connected to each other by an edge.

58. The computing system of claim 18, further including a user interface for receiving input from a user or a predetermined rule applied to the network to modify the network by adding an edge between two nodes or removing an edge between two nodes.

59. The computing system of claim 58, wherein the user interface displays a visual representation of the network, and visually indicating the values associated with the nodes.

60. The computing system of claim 59, wherein the user interface receives the input.