Method and system for extracting consistent disjoint set membership from multiple inconsistent data sources

• US 7,752,179 B1
• Filed: 02/24/2006
• Issued: 07/06/2010
• Est. Priority Date: 02/24/2006
• Status: Active Grant

• Current Assignee: Intuit, Inc.
• Original Assignee: Intuit, Inc.
• Inventors: Brown, Jeffrey H.
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Hicks; Michael J
• Application Number:
  US11/361,372
• Time in Patent Office: 1,593 Days
• Field of Search: 707/690, 707/692
• US Class Current: 707/690
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

A method for extracting a consistent set of entity identifiers including associating each of a first plurality of entity identifiers with at least one of a first plurality of GroupIDs, associating each of a second plurality of entity identifiers with at least one of a second plurality of GroupIDs, combining the first plurality of entity identifiers with the second plurality of entity identifiers to generate a third plurality of entity identifiers, where each of the third plurality of entity identifiers is associated with at least one of a third plurality of GroupIDs, linking at least one of the third plurality of GroupIDs with at least one of the first plurality of GroupIDs based on the third plurality of entity identifiers and the first plurality of entity identifiers, removing a contaminated entity identifier from the third plurality of entity identifiers to extract the consistent set of entity identifiers.

Claims

1. A computer implemented method for extracting a consistent set of entity identifiers comprising:

obtaining a first set of entity identifiers comprising a first plurality of groups of entity identifiers using a grouping process;

obtaining a second set of entity identifiers comprising a second plurality of groups of entity identifiers using the grouping process;

subsequent to the grouping process, removing an entity identifier associated with a set violation from the first set of entity identifiers and the second set of entity identifiers, wherein the set violation corresponds to the first and second set of entity identifiers pertaining to a same entity, wherein the first and second set of entity identifiers are not identical and each contain at least two entity identifiers;

associating each entity identifier from the first set of entity identifiers with at least one of a first plurality of GroupIDs, wherein each of the first plurality of GroupIDs is an entity identifier designated from among the first set of entity identifiers;

associating each entity identifier from the second set of entity identifiers with at least one of a second plurality of GroupIDs, wherein each of the second plurality of GroupIDs is an entity identifier designated from among the second set of entity identifiers;

linking at least one of the first plurality of GroupIDs having a common entity identifier with at least one of the second plurality of GroupIDs having the common entity identifier;

during the linking, identifying a contaminated entity identifier associated with the at least one of the first and second plurality of GroupIDs based on a violation of a linking policy, wherein the linking policy is violated when one of the first plurality of GroupIDs is linked to more than one of the second plurality of GroupIDs;

removing the contaminated entity identifier from the first and second set of entity identifiers based on the violation of the linking policy; and

combining the first set of entity identifiers with the second set of entity identifiers following the removal of the contaminated entity identifier to extract the consistent set of entity identifiers.

2. The computer implemented method of claim 1, further comprising:

retrieving a record using the consistent set of entity identifiers, wherein the record is associated with an entity identifier within the consistent set of entity identifiers.

3. The computer implemented method of claim 1, further comprising:

adding the entity identifier associated with the set violation to a datastore.

4. The computer implemented method of claim 1, wherein associating each entity identifier from the first set of entity identifiers with the at least one of the first plurality of GroupIDs comprises:

determining the entity identifier of lesser value from the first set of entity identifiers.

5. The computer implemented method of claim 1, wherein associating each entity identifier from the first set of entity identifiers with the at least one of the first plurality of GroupIDs comprises:

determining the entity identifier of greater value from the first set of entity identifiers.

6. The computer implemented method of claim 1, wherein combining the first set of entity identifiers with the second set of entity identifiers comprises:

performing a join operation on the first and second set of entity identifiers; and

performing a GroupID minimization operation on the consistent set of entity identifiers.

7. The computer implemented method of claim 1, wherein combining the first set of entity identifiers with the second set of entity identifiers comprises:

performing a join operation on the first and second set of entity identifiers; and

performing a GroupID maximization operation on the consistent set of entity identifiers.

8. The computer implemented method of claim 1, wherein the linking policy is further violated when one of the second plurality of GroupIDs is linked to more than one of the first plurality of GroupIDs.

9. A computer implemented method for extracting a consistent set of entity identifiers comprising:

obtaining a first set of entity identifiers comprising a first plurality of groups of entity identifiers using a grouping process;

obtaining a second set of entity identifiers comprising a second plurality of groups of entity identifiers using the grouping process;

subsequent to the grouping process, removing an entity identifier associated with a set violation from the first set of entity identifiers and the second set of entity identifiers, wherein the set violation corresponds to the first and second set of entity identifiers pertaining to a same entity, wherein the first and second set of entity identifiers are not identical and each contain at least two entity identifiers;

associating each entity identifier from the first set of entity identifiers with at least one of a first plurality of GroupIDs, wherein each of the first plurality of GroupIDs is an entity identifier designated from among the first set of entity identifiers;

associating each entity identifier from the second set of entity identifiers with at least one of a second plurality of GroupIDs, wherein each of the second plurality of GroupIDs is an entity identifier designated from among the second set of entity identifiers;

combining the first set of entity identifiers with the second set of entity identifiers to generate a third set of entity identifiers, wherein each of the third set of entity identifiers is associated with at least one of a third plurality of GroupIDs;

linking at least one of the third plurality of GroupIDs having a common entity identifier with at least one of the first plurality of GroupIDs having the common entity identifier;

during the linking, identifying a contaminated entity identifier associated with the at least one of the first and third plurality of GroupIDs based on a violation of a linking policy, wherein the linking policy is violated when one of the first plurality of GroupIDs is linked to more than one of the third plurality of GroupIDs;

removing the contaminated entity identifier from the first and third set of entity identifiers based on the violation of the linking policy; and

combining the first set of entity identifiers with the third set of entity identifiers following the removal of the contaminated entity identifier to extract the consistent set of entity identifiers.

10. The computer implemented method of claim 9, further comprising:

retrieving a record using the consistent set of entity identifiers, wherein the record is associated with an entity identifier within the consistent set of entity identifiers.

11. The computer implemented method of claim 9, further comprising:

adding the entity identifier associated with the set violation to a datastore.

12. The computer implemented method of claim 9, wherein associating each entity identifier from the first set of entity identifiers with the at least one of the first plurality of GroupIDs comprises:

determining the entity identifier of greater value from the first set of entity identifiers.

13. The computer implemented method of claim 9, wherein associating each entity identifier from the first set of entity identifiers with at least one of the first plurality of GroupIDs comprises:

determining the entity identifier of lesser value from the first set of entity identifiers.

14. The computer implemented method of claim 9, further comprising:

linking at least one of the third plurality of GroupIDs having the common entity identifier with at least one of the second plurality of GroupIDs having the common entity identifier based on the second and third set of entity identifiers.

15. The computer implemented method of claim 9, wherein combining the first set of entity identifiers with the second set of entity identifiers comprises:

performing a join operation on the first and second set of entity identifiers; and

performing a GroupID maximization operation on the third set of entity identifiers.

16. The computer implemented method of claim 9, wherein combining the first set of entity identifiers with the second set of entity identifiers comprises:

performing a join operation on the first and second set of entity identifiers; and

performing a GroupID minimization operation on the third set of entity identifiers.

17. The computer implemented method of claim 9, wherein the linking policy is further violated when one of the third plurality of GroupIDs is linked to more than one of the first plurality of GroupIDs.

18. A computer readable storage medium containing instructions for extracting a consistent set of entity identifiers, the instructions comprising functionality to:

obtain a first set of entity identifiers comprising a first plurality of groups of entity identifiers using a grouping process;

obtain a second set of entity identifiers comprising a second plurality of groups of entity identifiers using the grouping process;

subsequent to the grouping process, removing an entity identifier associated with a set violation from the first set of entity identifiers and the second set of entity identifiers, wherein the set violation corresponds to the first and second set of entity identifiers pertaining to a same entity, wherein the first and second set of entity identifiers are not identical and each contain at least two entity identifiers;

associate each entity identifier from the first set of entity identifiers with at least one of a first plurality of GroupIDs, wherein each of the first plurality of GroupIDs is an entity identifier designated from among the first set of entity identifiers;

associate each entity identifier from the second set of entity identifiers with at least one of a second plurality of GroupIDs, wherein each of the second plurality of GroupIDs is an entity identifier designated from among the second set of entity identifiers;

link at least one of the first plurality of GroupIDs having a common entity identifier with at least one of the second plurality of GroupIDs having the common entity identifier;

during the linking, identify a contaminated entity identifier associated with the at least one of the first and second plurality of GroupIDs based on a violation of a linking policy, wherein the linking policy is violated when one of the first plurality of GroupIDs is linked to more than one of the third plurality of GroupIDs;

remove the contaminated entity identifier from the first and second set of entity identifiers based on the violation of the linking policy; and

combine the first set of entity identifiers with the second set of entity identifiers following the removal of the contaminated entity identifier to extract the consistent set of entity identifiers.

19. The computer readable storage medium of claim 18, the instructions further comprising functionality to:

retrieve a record using the consistent set of entity identifiers, wherein the record is associated with an entity identifier within the consistent set of entity identifiers.

20. The computer readable storage medium of claim 18, the instructions further comprising functionality to:

add the entity identifier associated with the set violation to a datastore.

21. The computer readable storage medium of claim 18, the instructions to associate each entity identifier from the first set of entity identifiers with the at least one of the first plurality of GroupIDs comprise functionality to:

determine the entity identifier of greater value from the first set of entity identifiers.

22. The computer readable storage medium of claim 18, the instructions to associate each entity identifier from the first set of entity identifiers with the at least one of the first plurality of GroupIDs comprise functionality to:

determine the entity identifier of lesser value from the first set of entity identifiers.

23. The computer readable storage medium of claim 18, the instructions to combine the first set of entity identifiers with the second set of entity identifiers comprise functionality to:

perform a join operation on the first and second set of entity identifiers; and

perform a GroupID maximization operation on the consistent set of entity identifiers.

24. The computer readable storage medium of claim 18, the instructions to combine the first set of entity identifiers with the second set of entity identifiers comprise functionality to:

perform a join operation on the first and second set of entity identifiers; and

perform a GroupID minimization operation on the consistent set of entity identifiers.

25. The computer readable storage medium of claim 18, wherein the linking policy is further violated when one of the third plurality of GroupIDs is linked to more than one of the first plurality of GroupIDs.

26. A computer readable storage medium for extracting a consistent set of entity identifiers, the instructions comprising functionality to:

obtain a first set of entity identifiers comprising a first plurality of groups of entity identifiers using a grouping process;

obtain a second set of entity identifiers comprising a second plurality of groups of entity identifiers using the grouping process;

subsequent to the grouping process, removing an entity identifier associated with a set violation from the first set of entity identifiers and the second set of entity identifiers, wherein the set violation corresponds to the first and second set of entity identifiers pertaining to a same entity, wherein the first and second set of entity identifiers are not identical and each contain at least two entity identifiers;

associate each entity identifier from the first set of entity identifiers with at least one of a first plurality of GroupIDs following the removal of the entity identifier associated with the set violation, wherein each of the first plurality of GroupIDs is an entity identifier designated from among the first set of entity identifiers;

associate each entity identifier from a second set of entity identifiers with at least one of a second plurality of GroupIDs, wherein each of the second plurality of GroupIDs is an entity identifier designated from among the second set of entity identifiers;

combine the first set of entity identifiers with the second set of entity identifiers to generate a third set of entity identifiers, wherein each of the third set of entity identifiers is associated with at least one of a third plurality of GroupIDs;

link at least one of the third plurality of GroupIDs having a common entity identifier with at least one of the first plurality of GroupIDs having a common entity identifier;

during the linking, identify a contaminated entity identifier associated with the at least one of the first and third plurality of GroupIDs based on a violation of a linking policy, wherein the linking policy is violated when one of the first plurality of GroupIDs is linked to more than one of the third plurality of GroupIDs;

remove the contaminated entity identifier from the first and third set of entity identifiers based on the violation of the linking policy; and

combine the first set of entity identifiers with the third set of entity identifiers following the removal of the contaminated entity identifier to extract the consistent set of entity identifiers.

27. The computer readable storage medium of claim 26, the instructions further comprising functionality to:

retrieve a record using the consistent set of entity identifiers, wherein the record is associated with an entity identifier within the consistent set of entity identifiers.

28. The computer readable storage medium of claim 26, the instructions further comprising functionality to:

add the entity identifier associated with the set violation to a datastore.

29. The computer readable storage medium of claim 26, the instructions to associate each entity identifier from the first set of entity identifiers with at least one of the first plurality of GroupIDs comprise functionality to:

determine the entity identifier of greater value from the first set of entity identifiers.

30. The computer readable storage medium of claim 26, the instructions to associate each entity identifier from the first set of entity identifiers with at least one of the first plurality of GroupIDs comprise functionality to:

determine the entity identifier of lesser value from the first set of entity identifiers.

31. The computer readable storage medium of claim 26, the instructions further comprising functionality to:

link at least one of the third plurality of GroupIDs having the common entity identifier with at least one of the second plurality of GroupIDs having the common entity identifier based on the second and third set of entity identifiers.

32. The computer readable storage medium of claim 26, the instructions to combine the first set of entity identifiers with the second set of entity identifiers comprise functionality to:

perform a join operation on the first and second set of entity identifiers; and

perform a GroupID maximization operation on the third set of entity identifiers.

33. The computer readable storage medium of claim 26, the instructions to combine the first set of entity identifiers with the second set of entity identifiers comprise functionality to:

perform a join operation on the first and second set of entity identifiers; and

perform a GroupID minimization operation on the third set of entity identifiers.

34. The computer readable storage medium of claim 26, wherein the linking policy is further violated when one of the third plurality of GroupIDs is linked to more than one of the first plurality of GroupIDs.