DATA CLUSTERING BASED ON VARIANT TOKEN NETWORKS

• US 20130124524A1
• Filed: 11/15/2012
• Published: 05/16/2013
• 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
• Granted Patent: US 9,037,589 B2
• Time in Patent Office: Days
• 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, 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;

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.

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 1, 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.

4. The method of claim 1, 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.

5. The method of claim 4, 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.

6. 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 predetermined threshold.

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

8. 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.

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

10. The method of claim 9, further including receiving the input through the user interface.

11. A computer program stored on a computer-readable storage 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, 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;

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.

12. 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, 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;

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.

13. 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, 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;

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.