Methods and Systems for Discovery of Linkage Points Between Data Sources

• US 20140337331A1
• Filed: 05/07/2013
• Published: 11/13/2014
• Est. Priority Date: 05/07/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hassanzadeh, Oktie, Hernandez-Sherrington, Mauricio Antonio, Ho, Ching-Tien, Popa, Lucian
• Granted Patent: US 9,710,534 B2
• Time in Patent Office: Days
• US Class Current: 707/726
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Data records are linked across a plurality of datasets. Each dataset contains at least one data record, and each data record is associated with an entity and includes one or more attributes of that entity and a value for each attribute. Values associated with attributes are compared across datasets, and matching attributes having values that satisfy a predetermined similarity threshold are identified. In addition, linkage points between pairs of datasets are identified. Each linkage point links one or more pairs of data records. Each data record in the pair of data records is contained in one of a given pair of datasets, and each pair of data records is associated with a common entity having matching attributes in the given pair of datasets. Data records associated with the common entities are linked across datasets using the identified linkage points.

Claims

1. A method for linking data records across datasets, the method comprising:

identifying a plurality of datasets, each dataset comprising at least one data record, each data record associated with an entity and comprising one or more attributes of that entity and a value associated with each attribute;

comparing values associated with attributes across datasets;

identifying matching attributes having values that satisfy a predetermined similarity threshold;

identifying linkage points between pairs of datasets, each linkage point linking one or more pairs of data records, each data record in each pair of data records contained in one of a given pair of datasets and each pair of data records associated with a common entity having matching attributes in the given pair of datasets; and

linking data records associated with the common entities across datasets using the identified linkage points.

2. The method of claim 1, wherein the method further comprises transforming each data record in each dataset into one or more data record triples, each data record triple for a given data record comprising an identification of a given record, a given attribute within that data record and a value for the given attribute.

3. The method of claim 2, wherein the identification for the given record comprises an alpha-numeric designation.

4. The method of claim 2, wherein the method further comprises converting each value in each data record triple into one or more tokens.

5. The method of claim 4, wherein:

each value comprises a value string comprising at least one of alpha-numeric characters, non-alphanumeric characters and spaces; and

converting each value comprise;

placing the value string into the set of tokens without changes, transforming any upper case alpha-numeric character in the value string into a corresponding lower case alpha character, breaking the value string into a plurality of tokens defined by the spaces in the value string, replacing non-alphanumeric characters with spaces, breaking the value string into a plurality of tokens comprising all lowercase alpha-numeric strings of a predetermined length or combinations thereof.

6. The method of claim 4, wherein the method further comprises creating a token set for each attribute in a given data record, each token set comprising all tokens obtained from converting all values associated with a given attribute in the given data record into one or more tokens.

7. The method of claim 4, wherein the method further comprises creating a token set for each attribute in a given data set, each token set comprising all tokens obtain from converting all values associated with a given attribute in the given data set into one or more tokens.

8. The method of claim 1, wherein:

the method further comprises creating token sets for each attribute in each data record, each token set comprising a plurality of tokens obtain from converting all values associated with a given attribute into tokens; and

identifying matching attributes further comprises comparing the token sets of attributes using a set similarity function or an information retrieval type relevance function to identify pairs of attributes satisfying the predetermined similarity threshold.

9. The method of claim 8, wherein the set similarity function comprises intersection size, Jaccard similarity coefficient, Dice'"'"'s coefficient or maximum inclusion degree.

10. The method of claim 8, wherein the information retrieval type relevance function comprises cosine similarity with term frequency-inverse document frequency or Okapi BM25

11. The method of claim 8, wherein identifying matching attributes further comprises:

selecting an attribute in each one of a pair of datasets;

comparing the tokens sets for given data records for the selected attributes by comparing all tokens in the token sets to generate a similarity score; and

determining if the similarity score is above the predetermined similarity threshold.

12. The method of claim 8, wherein identifying matching attributes further comprises:

selecting an attribute in each one of a pair of datasets;

selecting one of more tokens from one of the token sets for given data records for the selected attributes;

searching the other token set for similar tokens to each one of the selected tokens using a value similarity function and a predefined threshold;

averaging the similarity scores for all returned similar tokens; and

determining if the average similarity score is above the predetermined similarity threshold.

13. The method of claim 1, wherein the method further comprises filtering the identified linkage points to remove false positives in the identified linkage points.

14. The method of claim 13, wherein filtering the identified linkage points further comprises filtering linkage points having a linkage set size below a given threshold, filtering linkage points wherein the linkage sets contain only a small percentage of records from one of the data sets or filtering linkage points having a strength below a predetermined level, the strength comprising a percentage of distinct records that appear in the linkage set.

15. A computer-readable storage medium containing a computer-readable code that when read by a computer causes the computer to perform a method for linking data records across datasets, the method comprising:

identifying a plurality of datasets, each dataset comprising at least one data record, each data record associated with an entity and comprising one or more attributes of that entity and a value associated with each attribute;

comparing values associated with attributes across datasets;

identifying matching attributes having values that satisfy a predetermined similarity threshold;

identifying linkage points between pairs of datasets, each linkage point linking one or more pairs of data records, each data record in each pair of data records contained in one of a given pair of datasets and each pair of data records associated with a common entity having matching attributes in the given pair of datasets; and

linking data records associated with the common entities across datasets using the identified linkage points.

16. The computer-readable storage medium of claim 15, wherein the method further comprises transforming each data record in each dataset into one or more data record triples, each data record triple for a given data record comprising an identification of a given record, a given attribute within that data record and a value for the given attribute.

17. The computer-readable storage medium of claim 16, wherein:

each value comprises a value string comprising at least one of alpha-numeric characters, non-alphanumeric characters and spaces; and

the method further comprises converting each value in each data record triple into one or more tokens;

placing the value string into the set of tokens without changes, transforming any upper case alpha-numeric character in the value string into a corresponding lower case alpha character, breaking the value string into a plurality of tokens defined by the spaces in the value string, replacing non-alphanumeric characters with spaces, breaking the value string into a plurality of tokens comprising all lowercase alpha-numeric strings of a predetermined length or combinations thereof.

18. The computer-readable storage medium of claim 17, wherein:

the method further comprises creating token sets for each attribute in each data record, each token set comprising a plurality of tokens obtained from converting all values associated with a given attribute into tokens; and

identifying matching attributes further comprises comparing the token sets of attributes using a set similarity function or an information retrieval type relevance function to identify pairs of attributes satisfying the predetermined similarity threshold.

19. The computer-readable storage medium of claim 17, wherein the method further comprises

filtering the identified linkage points to remove false positives in the identified linkage points by:

filtering linkage points having a linkage set size below a given threshold, filtering linkage points wherein the linkage sets contain only a small percentage of records from one of the data sets or filtering linkage points having a strength below a predetermined level, the strength comprising a percentage of distinct records that appear in the linkage set.