FACILITY FOR RECONCILIATION OF BUSINESS RECORDS USING GENETIC ALGORITHMS

• US 20110029467A1
• Filed: 07/30/2009
• Published: 02/03/2011
• Est. Priority Date: 07/30/2009
• Status: Active Grant

• Current Assignee: Marchex Incorporated
• Original Assignee: Marchex Incorporated
• Inventors: Aegard, John, Berk, Matthew, Spehr, Darren
• Granted Patent: US 8,583,571 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A facility for the reconciliation of data records pertaining to business entities. One or more fitness functions are applied to fields contained in two conflicting data records to assess the similarity of each field. The results of the fitness functions are then weighted and combined to assess the likelihood that the two data records are associated with the same business entity. When the weighted fitness functions are applied to conflicting data records, the fitness functions generate a confidence level that the compared records are associated with the same business entity. If the confidence level exceeds a certain threshold, the facility accepts that the data records refer to the same business entity and synthesizes a business record from the data records.

Claims

1. A computer-implemented method of matching and reconciling business records using fitness functions, the computer-implemented method comprising:

for each field in a first business record that is to be compared with a corresponding field in a second business record, selecting a production fitness function to be applied to compare the contents of the field in the first and second business records and a weight that is to be applied to the result of the applied production fitness function by;

applying test fitness functions to fields contained in a plurality of test business records to determine fitness function results, weighting each fitness function result by an associated weight, and calculating an overall performance of the test fitness functions based on the weighted fitness function results across the plurality of test business records;

repeating the application of test fitness functions until an overall performance of one or more weighted test fitness functions exceeds a first confidence threshold, wherein the test fitness functions and associated weights are modified for each repeat application; and

selecting at least one of the test fitness functions and weights that exceed the first confidence threshold as production fitness functions and weights;

applying the selected production fitness functions for each field in the first business record that is to be compared with a corresponding field in the second business record;

weighting the results of the applied production fitness functions to calculate a confidence level that the first business record and the second business record are associated with the same business entity; and

combining the first business record and the second business record into an authoritative business record if the calculated confidence level exceeds a second confidence threshold.

2. The computer-implemented method of claim 1, further comprising pre-processing the plurality of test business records to normalize the test business records before applying the test fitness functions.

3. The computer-implemented method of claim 1, further comprising pre-processing the first business record and second business record to normalize the business records before applying the production fitness functions.

4. The computer-implemented method of claim 3, wherein pre-processing comprises removing common words, removing punctuation, and removing words that specify a category.

5. The computer-implemented method of claim 3, wherein pre-processing comprises shortening long words to minimize the impact long words have on correlation.

6. The computer-implemented method of claim 3, wherein pre-processing comprises normalizing words and phrases.

7. The computer-implemented method of claim 1, wherein the test fitness functions are selected from the group consisting of an adjacency matrix fitness function and a tokenizing fitness function.

8. The computer-implemented method of claim 1, wherein the first confidence threshold is between 90 percent and 100 percent.

9. The computer-implemented method of claim 1, wherein the second confidence threshold is between 70 percent and 100 percent.

10. The computer-implemented method of claim 1, wherein merging the first business record and second business record comprises:

determining a reliability of a first data source for each field in the first business record;

determining a reliability of a second data source for each field in the second business record; and

selecting fields from the business record associated with the data source having a higher reliability for that field.

11. The computer-implemented method of claim 1, further comprising displaying the authoritative business record to consumers.

12. A system for matching and reconciling business records using fitness functions, the system comprising:

a genetic algorithm module that, for each field in a first business record that is to be compared with a corresponding field in a second business record, selects a production fitness function to be applied to compare the contents of the field in the first and second business records and a weight that is to be applied to the result of the applied production fitness function by;

applying test fitness functions to fields contained in a plurality of test business records to determine fitness function results, weighting each fitness function result by an associated weight, and calculating an overall performance of the test fitness functions based on the weighted fitness function results across the plurality of test business records;

repeating the application of test fitness functions until an overall performance of one or more weighted test fitness functions exceeds a first confidence threshold, wherein the test fitness functions and associated weights are modified for each repeat application; and

selecting at least one of the test fitness functions and weights that exceed the first confidence threshold as production fitness functions and weights;

a record matching module that applies the production fitness functions selected by the genetic algorithm module to each field in the first business record that is to be compared with a corresponding field in the second business record, and weights the results of the applied production fitness functions using the weights selected by the genetic algorithm module to calculate a confidence level that the first business record and the second business record are associated with the same business entity; and

a field selection module that merges the first business record and the second business record into an authoritative business record if the confidence level calculated by the record matching module exceeds a second confidence threshold.

13. The system of claim 12, further comprising a pre-processing module that pre-processes the plurality of test business records to normalize the business records before the genetic algorithm module applies the test fitness functions.

14. The system of claim 12, further comprising a pre-processing module that pre-processes the first business record and second business record to normalize the business records before the record matching module applies the production fitness functions.

15. The system of claim 14, wherein pre-processing comprises removing common words, removing punctuation, and removing words that specify a category.

16. The system of claim 14, wherein pre-processing comprises shortening long words to minimize the impact long words have on correlation.

17. The system of claim 14, wherein pre-processing comprises normalizing words and phrases.

18. The system of claim 12, wherein the test fitness functions are selected from the group consisting of an adjacency matrix fitness function and a tokenizing fitness function.

19. The system of claim 12, wherein the first confidence threshold is between 90 percent and 100 percent.

20. The system of claim 12, wherein the second confidence threshold is between 70 percent and 100 percent.

21. The system of claim 12, wherein the field selection module merges the first business record and second business record by:

determining a reliability of a first data source for each field in the first business record;

determining a reliability of a second data source for each field in the second business record; and

selecting fields from the business record associated with the data source having a higher reliability for that field.

22. A computer-implemented method of matching and reconciling business records using fitness functions, the computer-implemented method comprising:

for each field or concatenated fields in a first business record that are to be compared with a corresponding field or concatenated fields in a second business record, selecting a production fitness function to be applied to compare the contents of the field or concatenated fields in the first and second business records and a weight that is to be applied to the result of the applied production fitness function by;

repeatedly applying test fitness functions to fields or concatenated fields contained in a plurality of test business records and weighting the results until an overall performance of one or more weighted test fitness functions exceeds a first confidence threshold; and

selecting at least one of the test fitness functions and weights that exceed the first confidence threshold as production fitness functions and weights;

applying the selected production fitness functions to each field or concatenated fields in the first business record that are to be compared with a corresponding field or concatenated fields in the second business record;

weighting the results of the applied production fitness functions to calculate a confidence level that the first business record and the second business record are associated with the same business entity; and

flagging that the first business record and the second business record should be combined into an authoritative business record if the calculated confidence level exceeds a second confidence threshold.

23. The computer-implemented method of claim 22, further comprising pre-processing the plurality of test business records to normalize the test business records before applying the test fitness functions.

24. The computer-implemented method of claim 22, further comprising pre-processing the first business record and second business record to normalize the business records before applying the production fitness functions.

25. The computer-implemented method of claim 24, wherein pre-processing comprises removing common words, removing punctuation, and removing words that specify a category.

26. The computer-implemented method of claim 24, wherein pre-processing comprises shortening long words to minimize the impact long words have on correlation.

27. The computer-implemented method of claim 24, wherein pre-processing comprises normalizing words and phrases.

28. The computer-implemented method of claim 22, wherein the test fitness functions are selected from the group consisting of an adjacency matrix fitness function and a tokenizing fitness function.

29. The computer-implemented method of claim 22, wherein the first confidence threshold is between 90 percent and 100 percent.

30. The computer-implemented method of claim 22, wherein the second confidence threshold is between 70 percent and 100 percent.

31. The computer-implemented method of claim 22, further comprising merging a flagged first business record and a second business record into an authoritative business record.

32. The computer-implemented method of claim 31, wherein merging the first business record and the second business record comprises:

determining a reliability of a first data source for each field in the first business record;

determining a reliability of a second data source for each field in the second business record; and

selecting fields from the business record associated with the data source having a higher reliability for that field.

33. The computer-implemented method of claim 22, further comprising displaying the authoritative business record to consumers.

34. A system for matching and reconciling business records using fitness functions, the system comprising:

a genetic algorithm module that, for each field or concatenated fields in a first business record that are to be compared with a corresponding field or concatenated fields in a second business record, selects a production fitness function to be applied to compare the contents of the field or concatenated fields in the first and second business records and a weight that is to be applied to the result of the applied production fitness function by;

repeatedly applying test fitness functions to fields or concatenated fields contained in a plurality of test business records and weighting the results until an overall performance of one or more weighted test fitness functions exceeds a first confidence threshold; and

selecting at least one of the test fitness functions and weights that exceed the first confidence threshold as production fitness functions and weights; and

a record matching module that;

applies the production fitness functions selected by the genetic algorithm module to each field or concatenated fields in the first business record that are to be compared with a corresponding field or concatenated fields in the second business record;

weights the results of the applied production fitness functions to calculate a confidence level that the first business record and the second business record are associated with the same business entity; and

if the calculated confidence level exceeds a second confidence threshold, flags that the first business record and the second business record should be combined into an authoritative business record.

35. The system of claim 34, further comprising a pre-processing module that pre-processes the plurality of test business records to normalize the test business records before applying the test fitness functions.

36. The system of claim 34, further comprising a pre-processing module that pre-processes the first business record and second business record to normalize the business records before applying the production fitness functions.

37. The system of claim 36, wherein pre-processing comprises removing common words, removing punctuation, and removing words that specify a category.

38. The system of claim 36, wherein pre-processing comprises shortening long words to minimize the impact long words have on correlation.

39. The system of claim 36, wherein pre-processing comprises normalizing words and phrases.

40. The system of claim 34, wherein the test fitness functions are selected from the group consisting of an adjacency matrix fitness function and a tokenizing fitness function.

41. The system of claim 34, wherein the first confidence threshold is between 90 percent and 100 percent.

42. The system of claim 34, wherein the second confidence threshold is between 70 percent and 100 percent.

43. The system of claim 34, further comprising a field selection module that merges the flagged first business record and second business record into an authoritative business record.

44. The system of claim 43, wherein merging the first business record and the second business record comprises:

determining a reliability of a first data source for each field in the first business record;

determining a reliability of a second data source for each field in the second business record; and

selecting fields from the business record associated with the data source having a higher reliability for that field.