Methods and systems for hierarchical blocking

• US 9,830,377 B1
• Filed: 03/14/2014
• Issued: 11/28/2017
• Est. Priority Date: 04/26/2013
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Wal-Mart Stores Texas LLC (WalMart Inc.)
• Inventors: Ray, Andrew Benjamin, Troutman, Nathaniel Philip
• Primary Examiner(s): Morrison, Jay
• Assistant Examiner(s): Hoang, Ken
• Application Number:
  US14/213,951
• Time in Patent Office: 1,355 Days
• Field of Search: 707737, 707E17014, 707692, 707E17005, 707E17046, 707741, 707722, 707769, 707791, 707792, 707999005, 707E17001, 707E17002, 707E17044, 707E17045, 707E17048, 707E17051, 707E17054, 707E17055, 707E17083, 707690, 707695, 707718, 707747, 707752, 707780, 707796, 707797, 707809, 707822, 707827, 707999002, 707999003, 707999102, 709224, 709215, 709226, 706 12, 706 46, 706 48, 706 52
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Techniques for comparing customer records to identify linked customer records are provided. The techniques may include a computer system identifying a target group of electronic customer records which have data pertaining to a customer, receiving a hierarchical blocker, and analyzing a customer record against the hierarchical blocker and extracting one or more data values from data fields identified by the hierarchical blocker. The computer system may create block keys from the extracted data values, associate the block keys with the customer record, create a block key group of customer records which are associated with a particular block key, and compare pairs of records from the block key group to identify records which are likely to be linked records because they pertain to a single customer entity.

Claims

1. A computer implemented method comprising:

a computer system identifying a target group of electronic customer records, each electronic customer record having data fields containing data pertaining to a customer;

the computer system receiving a hierarchical blocker function, wherein the hierarchical blocker function comprises a blocker function that includes a first combination blocker function that operates on multiple data fields within a customer record to generate at least one intermediate blocker result, and a second combination blocker function that operates on the at least one intermediate blocker result to generate multiple resultant blockers, and wherein a resultant blocker of the multiple resultant blockers identifies one or more data fields within a customer record;

the computer system analyzing a customer record against the multiple resultant blockers and extracting one or more data values from the one or more data fields of the customer record identified by the multiple resultant blockers;

the computer system creating multiple block keys from the one or more extracted data values corresponding to the multiple resultant blockers;

the computer system associating the multiple block keys with the customer record;

the computer system creating a block key group of customer records, wherein each customer record in the block key group is associated with a particular one of the multiple block keys; and

the computer system comparing pairs of records from the block key group to identify records that are likely to be linked records, wherein linked records comprise two or more electronic customer records which pertain to a single customer entity.

2. The method of claim 1, wherein the method further comprises:

the computer system parsing the hierarchical blocker function to generate the multiple resultant blockers from the hierarchical blocker; and

the computer system analyzing a customer record against the resultant blocker and extracting one or more data values from the one or more data fields identified by the resultant blocker.

3. The method of claim 1, wherein the resultant blocker is a combination of multiple individual blockers which each identify a different data field within a customer record.

4. The method of claim 1, wherein the first combination blocker function and the second combination blocker function are selected from the group consisting of:

UNION, CROSS-PRODUCT, and CHOOSE-K combination blocker functions;

wherein the UNION combination blocker function is a blocker function which creates a plurality of resultant blockers from each member of a list of specified blockers;

wherein the CROSS-PRODUCT combination blocker function is a blocker function which creates a single resultant blocker which is a combination of each member of a list of specified blockers; and

wherein the CHOOSE-K combination blocker function is a blocker function which allows K to be specified as a number and which creates a plurality of resultant blockers which comprises each possible unique combination of K number of blockers from a list of specified blockers.

5. The method of claim 1, wherein the second combination blocker function comprises a UNION combination blocker function and the first combination blocker function comprises a CROSS-PRODUCT combination blocker function;

wherein the UNION combination blocker function is a blocker function which creates a plurality of resultant blockers from each member of a list of specified blockers; and

wherein the CROSS-PRODUCT combination blocker function is a blocker function which creates a single resultant blocker which is a combination of each member of a list of specified blockers.

6. The method of claim 1, wherein the second combination blocker function comprises a UNION combination blocker function and the first combination blocker function comprises a CHOOSE-K combination blocker function;

wherein the UNION combination blocker function is a blocker function which creates a plurality of resultant blockers from each member of a list of specified blockers; and

wherein the CHOOSE-K combination blocker function is a blocker function which allows K to be specified as a number and which creates a plurality of resultant blockers which comprises each possible unique combination of K number of blockers from a list of specified blockers.

7. The method of claim 1, wherein the method further comprises:

the computer system analyzing electronic customer records from within the target group of electronic customer records to, for each electronic customer record within the target group of electronic customer records, identify a plurality of block keys which result from the hierarchical blocker, wherein each block key of the plurality of block keys comprises data values from an electronic customer record corresponding to data fields identified by resultant blockers from the hierarchical blocker; and

the computer system identifying a block key group of electronic customer records, the block key group of electronic customer records comprising electronic customer records containing a single block key.

8. The method of claim 7, wherein the method further comprises the computer system comparing all possible pairs of electronic customer records from the block key group of electronic customer records to identify linked records.

9. The method of claim 8, wherein the computer system does not compare pairs of electronic customer records which are not found within a block key group of electronic customer records associated with a single block key.

10. A computer system comprising:

a computer system including a computer processor and memory operatively coupled to the computer processor, the memory storing a records processing module programmed to;

identify a target group of electronic customer records, each electronic customer record having data fields containing data pertaining to a customer;

receive a hierarchical blocker function, wherein the hierarchical blocker function comprises a blocker function that includes a first combination blocker function that operates on multiple data fields within a customer record to generate at least one intermediate blocker result, and a second combination blocker function that operates on the at least one intermediate blocker result to generate multiple resultant blockers, wherein a resultant blocker of the multiple resultant blockers identifies one or more data fields within a customer record;

analyze a customer record against the multiple resultant blockers and extract one or more data values from the one or more data fields identified by the multiple resultant blockers;

create multiple block keys corresponding to the multiple resultant blockers from the one or more extracted data values;

associate the multiple block keys with the customer record;

create a block key group of customer records, wherein each customer record in the block key group is associated with a particular one of the multiple block keys; and

compare pairs of records from the block key group to identify records that are likely to be linked records, wherein linked records comprise two or more electronic customer records that pertain to a single customer entity.

11. The system of claim 10, wherein the computer is further programmed to:

parse the hierarchical blocker function to generate the multiple resultant blockers from the hierarchical blocker; and

analyze a customer record against the resultant blocker and extracting one or more data values from the one or more data fields identified by the resultant blocker.

12. The system of claim 10, wherein the resultant blocker is a combination of multiple individual blockers which each identify a different data field within a customer record.

13. The system of claim 10, wherein the first combination blocker function and the second combination blocker function are selected from the group consisting of:

UNION, CROSS-PRODUCT, and CHOOSE-K combination blockers blocker functions;

wherein the UNION combination blocker function is a blocker function which creates a plurality of resultant blockers from each member of a list of specified blockers;

wherein the CROSS-PRODUCT combination blocker function is a blocker function which creates a single resultant blocker which is a combination of each member of a list of specified blockers; and

wherein the CHOOSE-K combination blocker function is a blocker function which allows K to be specified as a number and which creates a plurality of resultant blockers which comprises each possible unique combination of K number of blockers from a list of specified blockers.

14. The system of claim 10, wherein the second combination blocker function comprises a UNION combination blocker function and the first combination blocker function comprises a CROSS-PRODUCT combination blocker function;

wherein the UNION combination blocker function is a blocker function which creates a plurality of resultant blockers from each member of a list of specified blockers; and

wherein the CROSS-PRODUCT combination blocker function is a blocker function which creates a single resultant blocker which is a combination of each member of a list of specified blockers.

15. The system of claim 10, wherein the second combination blocker function comprises a UNION combination blocker function and the first combination blocker function comprises a CHOOSE-K combination blocker function;

wherein the UNION combination blocker function is a blocker function which creates a plurality of resultant blockers from each member of a list of specified blockers; and

wherein the CHOOSE-K combination blocker function is a blocker function which allows K to be specified as a number and which creates a plurality of resultant blockers which comprises each possible unique combination of K number of blockers from a list of specified blockers.

16. The system of claim 10, wherein the computer is further programmed to:

analyze electronic customer records from within the target group of electronic customer records to, for each electronic customer record within the target group of electronic customer records, identify a plurality of block keys which result from the hierarchical blocker, wherein each block key of the plurality of block keys comprises data values from an electronic customer record corresponding to data fields identified by resultant blockers from the hierarchical blocker; and

identify a block key group of electronic customer records, the block key group of electronic customer records comprising electronic customer records containing a single block key.

17. The system of claim 16, wherein the computer is further programmed to:

compare all possible pairs of electronic customer records from the block key group of electronic customer records to identify linked records.

18. The system of claim 17, wherein the computer system is programmed to not compare pairs of electronic customer records which are not found within a block key group of electronic customer records associated with a single block key.