Case Study- Developing solution for a large volume data matching requirement.
This writeup elaborates the solution that was developed to implement the OLO profile creation requirement in PLT application (name changed). I was associated with the solution development, in my capacity as the Development Manager of the application development team. I have tried to reconstruct the problem & the challenges that were associated the requirement & thoughts that went into developing the optimum solution to the problem.
This problem is closely related at a generic level, with the challenges associated with establishing relationship between two entities through a data matching process. The challenge gets accentuated; if entities to be matched have a very large data sizes (in excess of 100 Million Records). There are commercial tools available which provide functionality to address this specific problem, but most of them have limitation with handling of large volume of data. And in most of the cases these tools have to be used in conjunction with a custom pre-processing logic that works upon the ‘Large Volume’ data sources & makes the commercial matching tool usable accommodating its data volume handling limitations.
The OLO profile creation for PLT application falls in this problem genre. The solution elaborated in this writeup, can be reused without an iota of botheration of infringement of any protected intellectual property rights & things similar to these. Being a beneficiary of benevolent Open Software movement, this is a small contribution to the cause.
Problem Definition
PLT application is required to create License Ownership (OLO) profiles. These profiles were to be created by matching the Agreement data with the Organization data. Agreement & Organization are two different data sources. The OLO Profile would more be like the relationship entity, maintaining the relationship definition between Agreement & Organisation entities. Organisation & Agreements share a 1: N relationship, with an organisation instance being linked to multiple agreement instances. And an agreement instance can be linked to only one organisation instance.
The matching of the records from the Agreement & Organization data sources can happen through common attributes. Common attributes like organization name, country, state, zip are present in both Agreement and Organization records.
The initial creation of the OLO profiles would need to match close to 100 million records of Agreement data with 10 million records of Organizational data.
Both the Agreement & the Organization data source would get updated on a periodical basis, with new records being added. The rate of addition/increase would be in the range of 5 % to 10 % on a quarterly year time period. The PLT application would have to create new version of the OLO profiles with every new data updates to the Agreement & Organization data sources.
The PLT application has the option of performing the data matching processing through a tool called Thallium (name changed). Thallium can be configured to perform data matching, through configurable matching rules. The matching rules can be defined using the common attributes.
The Thallium tool however has a finite limitation to the data that it can handle while performing data matching. The Thallium tool can only handle data volumes up to of 20 million records in single data matching run.
This means, usage of just the Thallium tool would not meet the PLT application requirements. The PLT application is required to handle data in excess of 100 million in each data matching run.
The matching of the records from the Agreement & Organization data sources can happen through common attributes. Common attributes like organization name, country, state, zip are present in both Agreement and Organization records.
The initial creation of the OLO profiles would need to match close to 100 million records of Agreement data with 10 million records of Organizational data.
Both the Agreement & the Organization data source would get updated on a periodical basis, with new records being added. The rate of addition/increase would be in the range of 5 % to 10 % on a quarterly year time period. The PLT application would have to create new version of the OLO profiles with every new data updates to the Agreement & Organization data sources.
The PLT application has the option of performing the data matching processing through a tool called Thallium (name changed). Thallium can be configured to perform data matching, through configurable matching rules. The matching rules can be defined using the common attributes.
The Thallium tool however has a finite limitation to the data that it can handle while performing data matching. The Thallium tool can only handle data volumes up to of 20 million records in single data matching run.
This means, usage of just the Thallium tool would not meet the PLT application requirements. The PLT application is required to handle data in excess of 100 million in each data matching run.
Solution
A pre-processing algorithm was developed, that would split the quantum of data to be matched into multiple data buckets. Each of these data buckets would accommodate the data handling limitation of Thallium tool. These data buckets would be run through the Thallium tool in a sequential manner, to perform all the required data matching and create the OLO profiles. The pre-processing logic will allow for the use of Thallium tool, accommodate its limitations and at the same time also not dilute the business requirement for performing the data mapping.
The pre-processing algorithm can be split in two parts,
->Segregated Data Buckets, to minimize the data sizes for data matching runs.
->Delta Bucketing, to minimize the data matching processing for data increments.
Segregating Data Buckets
This processing would segregate Organisation and Agreement data into groups based on the key common attributes. The same common attributes that are used for configuring the data matching behavior of the Thallium tool.
Each grouping would be a collation of the Agreement & Organisation data that have a higher probability of the getting matched up. The data group would exclude to a very large extend grouping of data that will never get matched.
E.g., the segregation logic will put the agreement & organization records with same country value of USA in the same grouping. The records with mismatching country value will not be grouped together. Country is one of the common attributes. The segregation can be made more fine grained by combining more common attributes (Country, State, Zip Code). The fine graining will further add in improving the probability of data matches with in a grouping.
This segregation & grouping of data will help in reducing the processing requirements on the Thallium matching tool, as matching of dissimilar records is eliminated to a large extend.
The grouping also helps accommodating the 20 Million data volume handling limitations of Thallium. The 100 Million of Agreement & 10 Million Organisation data will be bunched in multiple much smaller data groups. These multiple data groups will be run sequentially through the Thallium Tool one at a time
Delta Bucketing
The data increments to Agreement & Organisation data sources would necessitate creation of the new version of OLO profiles. Recreating the initial data matching execution, for every incremental data updates would place a severe load on the processing resources. More importantly, if an initial run type is repeated, the processing result gathered through earlier runs would simply be wasted away.
The ‘Delta Bucketing’ logic will help in making the incremental data matching runs to focus only on the new data increments that have happened. The incremental data matching execution would consume less amount of processing time compared to a full re-run of data matching and will also help in retaining the processing results derived from previous data matching runs.
The data from the Agreement and Organisation data sources will be selectively grouped using the following logic,
-> All updated / newly added (from the earlier data matching runs) Agreement records should be compared against all the organization records from the same runtime bucket ranges ( the segregated data buckets)
-> All unmatched (unaltered) agreement records from the earlier data matching run should be compared against the modified / newly added organization records from the same runtime bucket ranges ( the segregated data buckets)
The efficacy of the selective grouping can be demonstrated through the following mathematical model.
Assume that a initial version of OLO Profiles (1.0) was created by running the data matching algorithm over Agreements data sources containing X records and Organisation data sources containing Y records. And after the initial data matching run there were X/4 agreement records that remained unmatched to any of the existing organisation records.
Since the initial data matching run, W new records were added to Agreement data source and Z new records were added to the Organisation data source.
Creation of the new version of the OLO versions, by repeating a full run would mean that the data matching would need to happen on (X+W) and (Y+Z) set of records. The data matching execution would need to perform (X+W) * (Y+Z) data matches to determine the new OLO version.
With Delta Bucketing logic the data matching would need to perform W*(Y+Z) + (X/4)*Z data matches to determine the new OLO version
Repeated Full Run- Equation 1
(X+W)*(Y+Z) = XY+XZ+WY+WZ
Delta Bucketing- Equation 2
W*(Y+Z) + (X/4)*Z = WY+WZ+ZX/4
‘Delta Bucketing’ is superior to the ‘Repeated Full Run’ as the records to be matched will be lesser by (XY) + (3/4) ZX (Derived comparing equation 1 & 2).
In other words the ‘Delta Bucketing’ eliminates the redundant & useless matching of data records.
->X*Y this would be equivalent to repeating the earlier matching run. As the results of the previous run are already available, re-run of the data matches would be a wasted effort. This wastage is eliminated by the ‘Delta Bucketing’ processing logic.
-> (3/4X) * Z this would be equivalent to matching agreements that have already been matched & linked to organisation in the previous run. This is a wasted run, as the single instance of agreement can be linked to only one instance of an organisation (Organisation -1:Nà Agreements).
Credits
Goes without saying, besides me there were many other contributors to the development of this solution. By authoring this write up I merely claim to be the story teller of a interesting solution that was implemented by the PLT team.
The ‘Delta Bucketing’ logic will help in making the incremental data matching runs to focus only on the new data increments that have happened. The incremental data matching execution would consume less amount of processing time compared to a full re-run of data matching and will also help in retaining the processing results derived from previous data matching runs.
The data from the Agreement and Organisation data sources will be selectively grouped using the following logic,
-> All updated / newly added (from the earlier data matching runs) Agreement records should be compared against all the organization records from the same runtime bucket ranges ( the segregated data buckets)
-> All unmatched (unaltered) agreement records from the earlier data matching run should be compared against the modified / newly added organization records from the same runtime bucket ranges ( the segregated data buckets)
The efficacy of the selective grouping can be demonstrated through the following mathematical model.
Assume that a initial version of OLO Profiles (1.0) was created by running the data matching algorithm over Agreements data sources containing X records and Organisation data sources containing Y records. And after the initial data matching run there were X/4 agreement records that remained unmatched to any of the existing organisation records.
Since the initial data matching run, W new records were added to Agreement data source and Z new records were added to the Organisation data source.
Creation of the new version of the OLO versions, by repeating a full run would mean that the data matching would need to happen on (X+W) and (Y+Z) set of records. The data matching execution would need to perform (X+W) * (Y+Z) data matches to determine the new OLO version.
With Delta Bucketing logic the data matching would need to perform W*(Y+Z) + (X/4)*Z data matches to determine the new OLO version
Repeated Full Run- Equation 1
(X+W)*(Y+Z) = XY+XZ+WY+WZ
Delta Bucketing- Equation 2
W*(Y+Z) + (X/4)*Z = WY+WZ+ZX/4
‘Delta Bucketing’ is superior to the ‘Repeated Full Run’ as the records to be matched will be lesser by (XY) + (3/4) ZX (Derived comparing equation 1 & 2).
In other words the ‘Delta Bucketing’ eliminates the redundant & useless matching of data records.
->X*Y this would be equivalent to repeating the earlier matching run. As the results of the previous run are already available, re-run of the data matches would be a wasted effort. This wastage is eliminated by the ‘Delta Bucketing’ processing logic.
-> (3/4X) * Z this would be equivalent to matching agreements that have already been matched & linked to organisation in the previous run. This is a wasted run, as the single instance of agreement can be linked to only one instance of an organisation (Organisation -1:Nà Agreements).
Credits
Goes without saying, besides me there were many other contributors to the development of this solution. By authoring this write up I merely claim to be the story teller of a interesting solution that was implemented by the PLT team.
No comments:
Post a Comment