Managing entities within a database

• US 8,370,355 B2
• Filed: 03/27/2008
• Issued: 02/05/2013
• Est. Priority Date: 03/29/2007
• Status: Expired due to Fees

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Harger, Douglas Scott, Jones, Erik, Seabolt, Edward
• Primary Examiner(s): Lee, Wilson
• Application Number:
  US12/056,720
• Publication Number:
  US 20080243885A1
• Time in Patent Office: 1,776 Days
• Field of Search: 707/616, 707/640, 707/641, 707624-627, 707713-714, 707737-740, 707/700, 707/741, 707/747, 707/235, 707/238, 707245-247, 707/214, 707/219, 709224-226, 709/214, 709/219, 709/200, 709/245, 709/246, 709/235, 709/238, 706/15, 706/45
• US Class Current: 707/737
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases

Abstract

Embodiments of a method for managing entities include candidate selection by a transitive bucketing process where at least one attribute of an initial data record is used to determine a set of candidate data records corresponding to the initial data record. For each candidate data record thus determined, additional candidate data record(s) may be determined using attribute(s) not used in linking the candidate data record to the initial data record. This process may be repeated until no more candidate data records are returned. The initial data record and related candidates thus determined are then resolved into group entities, each having member records that match one another above a certain threshold. If no match is found, a group entity comprising a single data record may be created. These group entities are then reconciled with other entities in a master entity index system.

Claims

1. A method for managing entities in a master entity index system, comprising:

determining a set of candidate data records based on at least one attribute of an initial data record;

performing a transitive bucketing process to determine additional candidate data records based on selective attributes of the set of candidate data records;

repeating the transitive bucketing process with a set of selective attributes of the additional candidate data records determined in a preceding iteration of the transitive bucketing process until no more candidate data records are returned, wherein the set of selective attributes for a repeated iteration of the transitive bucketing process is different than the set of selective attributes for the preceding iteration;

resolving the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process into group entities; and

reconciling the group entities with entities in the master entity index system.

2. The method of claim 1, further comprising receiving the initial data record and a set of attributes associated therewith, wherein the set of attributes includes the at least one attribute.

3. The method of claim 1, further comprising comparing the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process.

4. The method of claim 3, further comprising generating an associated score indicating a confidence level or likelihood to match between two data records selected from the group consisting of the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process.

5. The method of claim 1, wherein each of the group entities comprises at least one data record and wherein, for each of the group entities having two or more data records, the two or more data records match one another above a predetermined threshold.

6. The method of claim 1, wherein the selective attributes of the set of candidate data records utilized in determinining the additional candidate data records are different from the at least one attribute of the initial data record utilized in determining the set of candidate data records.

7. The method of claim 1, wherein each of the set of candidate data records has an attribute value that exactly matches a value of the at least one attribute of the initial data record.

8. The method of claim 1, further comprising introducing a rule to change a relationship between two data records selected from the group consisting of the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process.

9. The method of claim 1, wherein at least one data record selected from the group consisting of the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process participates in two or more of the group entities.

21. The method of claim 1, wherein the group entities are generated on the fly or persisted in a data store.

10. A computer-readable storage medium carrying computer-readable instructions executable by a processor to implement a method for managing entities in a master entity index system, the method comprising:

determining a set of candidate data records based on at least one attribute of an initial data record;

performing a transitive bucketing process to determine additional candidate data records based on selective attributes of the set of candidate data records;

repeating the transitive bucketing process with a set of selective attributes of the additional candidate data records determined in a preceding iteration of the transitive bucketing process until no more candidate data records are returned, wherein the set of selective attributes for a repeated iteration of the transitive bucketing process is different than the set of selective attributes for the preceding iteration;

resolving the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process into group entities; and

reconciling the group entities with entities in the master entity index system.

11. The computer-readable storage medium of claim 10, wherein the computer-readable instructions are further executable by the processor to compare the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process and generate an associated score indicating a confidence level or likelihood to match between one another.

12. The computer-readable storage medium of claim 10, wherein each of the group entities comprises at least one data record and wherein, for each of the group entities having two or more data records, the two or more data records match one another above a predetermined threshold.

13. The computer-readable storage medium of claim 10, wherein the selective attributes of the set of candidate data records utilized in determining the additional candidate data records are different from the at least one attribute of the initial data record utilized in determining the set of candidate data records.

14. The computer-readable storage medium of claim 10, wherein each of the set of candidate data records has an attribute value that exactly matches a value of the at least one attribute of the initial data record.

15. The computer-readable storage medium of claim 10, wherein the computer-readable instructions are further executable by the processor to change a relationship between two data records selected from the group consisting of the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process.

16. The computer-readable storage medium of claim 10, wherein at least one data record selected from the group consisting of the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process participates in two or more of the group entities.

22. The computer-readable storage medium of claim 10, wherein the computer-readable instructions are further executable by the processor to receive the initial data record and a set of attributes associated therewith, wherein the set of attributes includes the at least one attribute.

23. The computer-readable storage medium of claim 10, wherein the group entities are generated on the fly or persisted in a data store.

17. A system, comprising:

a processor; and

a computer-readable storage medium accessible by the processor and carrying computer-readable instructions executable by the processor to implement a method for managing entities in the system, the method comprising;

determining a set of candidate data records based on at least one attribute of an initial data record;

performing a transitive bucketing process to determine additional candidate data records based on selective attributes of the set of candidate data records;

repeating the transitive bucketing process with a set of selective attributes of the additional candidate data records determined in a preceding iteration of the transitive bucketing process until no more candidate data records are returned, wherein the set of selective attributes for a repeated iteration of the transitive bucketing process is different than the set of selective attributes for the preceding iteration;

resolving the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process into group entities; and

reconciling the group entities with entities in the system.

18. The system of claim 17, where the group entities are generated on the fly or persisted in a data store accessible by the processor.

19. The system of claim 17, wherein each of the group entities comprises at least one data record and wherein, for each of the group entities having two or more data records, the two or more data records match one another above a predetermined threshold.

20. The system of claim 17, wherein at least one data record selected from the group consisting of the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process participates in two or more of the group entities.

24. The system of claim 17, wherein the method further comprises receiving the initial data record and a set of attributes associated therewith, wherein the set of attributes includes the at least one attribute.

25. The system of claim 17, wherein the method further comprises comparing the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process and generating an associated score indicating a confidence level or likelihood to match between one another.

26. The system of claim 17, wherein the selective attributes of the set of candidate data records utilized in determining the additional candidate data records are different from the at least one attribute of the initial data record utilized in determining the set of candidate data records.

27. The system of claim 17, wherein each of the set of candidate data records has an attribute value that exactly matches a value of the at least one attribute of the initial data record.

28. The system of claim 17, wherein the method further comprises changing a relationship between two data records selected from the group consisting of the initial data record, the set of candidate data records, and any additional candidate data records determined via the transitive bucketing process.