Hierarchical drift detection of data sets

• US 20060020594A1
• Filed: 07/21/2004
• Published: 01/26/2006
• Est. Priority Date: 07/21/2004
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Garg, Neeraj, Daly, Michael T., Jayaram, Mahesh, Deb, Indrojit N., Rajasekaran, Kulothungan
• Application Number:
  US10/896,619
• Publication Number:
  US 20060020594A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

The present leverages data hierarchies to provide a systematic means to determine data differences between equivalent data. This allows disparate data storage systems to efficiently determine divergent data locations by utilizing, for example, data signatures representative of varying degrees of data granularity. Comparative analysis can then be performed between the databases by employing an iterative approach until the desired level of data granularity is obtained. This allows, in one instance of the present invention, discrepant data to be determined without the transfer of large amounts of data and without requiring homogeneous data storage systems. Another instance of the present invention utilizes equivalent logical data views from non-identical data sets to determine data discrepancies. Yet another instance of the present invention determines discrepancies of a federated and/or integrated data system by employing reversible data statistical signatures, providing a simplistic transfer protocol and sheltering each data system from the other'"'"'s complexities.

Claims

1. A system that facilitates data discrepancy determination, comprising:

a partitioning component that utilizes a hierarchical structure of a data set to partition data at various levels of the data structure;

a digest component that condenses at least one data partition provided by the partitioning component;

a signature component that determines at least one signature of at least one data partition digested by the digest component; and

a comparison component that compares a data digest signature with at least one other data digest signature to ascertain if mismatched data exists;

the other data digest signature representative of data that a user desires to be equivalent to data associated with the data digest signature.

2. The system of claim 1 further comprising:

an interface component that transfers data signatures between a plurality of data entities to facilitate comparison of the data signatures.

3. The system of claim 1 further comprising:

a statistical signature component that calculates a statistical signature utilizing the data digest signatures provided by the signature component;

the statistical signature representative of a plurality of data digests without a dependency on the data'"'"'s hierarchical structure.

4. The system of claim 3 further comprising:

a regression component that utilizes the statistical signature to determine data signatures for data partitions of at least one hierarchical data structure to facilitate in isolating mismatched data.

5. The system of claim 1 further comprising:

an iteration component that continually converges the data discrepancy determination until at least one selected from the group consisting of a lowest mismatched data structure level is obtained and a manageable mismatched data size is obtained.

6. The system of claim 5, the manageable mismatched data size comprising a data size that can be transferred between data entities without substantial costs.

7. The system of claim 1 further comprising:

a signature compilation component that utilizes a lower level mismatched data partition signature combined with a higher level data partition signature to create a compiled signature for utilization by the comparison component.

8. The system of claim 1 comprising at least one selected from the group consisting of a federated system and an integrated system.

9. The system of claim 1 further comprising:

a logical view component that establishes a logical data view for a plurality of disparate data sets to enable data discrepancy determination of equivocal data.

28. A computer readable medium having stored thereon computer executable components of the system of claim 1.

30. A device employing the system of claim 1 comprising at least one selected from the group consisting of a computer, a server, and a handheld electronic device.

10. A method for facilitating data discrepancy determination, comprising:

partitioning data into chunks and assigning signatures to the respective chunks;

determining discrepancy in a subset of the chunks via a signature comparison;

further partitioning the chunk subset and assigning new signatures to the partitioned chunk subsets; and

repeating the discrepancy determination, partitioning, and assignment of new signatures until convergence upon specific non-matching records and/or data is achieved.

11. The method of claim 10, wherein the method is applied between a plurality of entities.

12. The method of claim 10, further comprising:

reversing a data signature to facilitate in locating mismatched data for a given federated data structure.

13. The method of claim 10, wherein at least two disparate entities successively perform the determination, partitioning, and assignment of new signatures.

14. The method of claim 13, wherein the entities are maintaining databases.

15. The method of claim 13, wherein the collection of data for at least one entity is different.

16. The method of claim 13, wherein the collection of data for at least one entity is equivalent but not identical.

17. The method of claim 10, wherein each new signature has a first element that identifies a respective chunk and a second element is a digest of the respective chunk.

18. The method of claim 17, wherein the digest is a cyclical redundancy check (CRC).

19. The method of claim 17, wherein the digest is a digital signature.

20. The method of claim 17, wherein the digest is a domain specific digital signature.

21. The method of claim 20, the signature is comprised of a signature that incorporates at least one lower level data chunk signature with at least one higher level data chunk signature.

22. The method of claim 10, further comprising:

correcting the non-matching records and/or data via conflict resolution.

23. The method of claim 22, wherein the conflict resolution is based on random decision.

24. The method of claim 22, wherein the conflict resolution is based on manual intervention.

25. The method of claim 22, wherein the conflict resolution utilizes a repair function that handles data that is not identical.

29. A device employing the method of claim 10 comprising at least one selected from the group consisting of a computer, a server, and a handheld electronic device.

26. A system that facilitates data discrepancy determination, comprising:

means for partitioning a data set at various levels of a hierarchical data structure;

means for digesting at least one partition of a data set;

means for determining at least one data signature of at least one digested data partition; and

means for comparing a data digest signature with at least one other data digest signature to ascertain if mismatched data exists, the other data digest signature representative of data that a user desires to be equivalent to data associated with the data digest signature.

27. A data packet, transmitted between two or more computer components, that facilitates data discrepancy determination, the data packet comprising, at least in part, information relating to a data discrepancy determination system that utilizes, at least in part, at least one data signature representative of at least one data partition based, at least in part, on a hierarchical structure of a data set and utilized in an iterative process to isolate mismatched data.