Finding similarities in data records

• US 20070083511A1
• Filed: 10/11/2005
• Published: 04/12/2007
• Est. Priority Date: 10/11/2005
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mao, Yi, Kapoor, Rahul
• Application Number:
  US11/247,604
• Publication Number:
  US 20070083511A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors

Abstract

System(s) and/or method(s) (“tools”) are described that enable actions to be reused that are common to multiple similarity functions. The tools may do so, in one embodiment, by composing similarity functions into a single, composed function that performs actions once that are common to multiple similarity functions. This composed function may also permit data to be analyzed in one pass and/or render unnecessary a merge operation. The tools may also enable actions to be reused when a similarity function is performed multiple times. The tools may do so, in one embodiment, by retaining a result of performing an action and using that result when performing the similarity function again. The tools may also enable records to be compared using a flip-window algorithm. This algorithm may be an efficient way in which to compare records in a table to determine which of those records are similar or duplicates.

Claims

1. A computer-implemented method comprising:

executing an action on first data and second data as part of a first similarity function, the first similarity function performed to determine a similarity between the first data and the second data; and

using a result of executing the action to enable;

execution of the first similarity function, where the first similarity function is performed to determine a similarity between the first data and third data, without having to execute the action on the first data;

or

execution of a second similarity function that;

is different from the first similarity function;

requires execution of the action on the first data or the second data; and

is performed to determine a similarity between the first data and the second data or fourth data without having to execute the action on the first data or the second data.

2. The method of claim 1, further comprising executing the second similarity function to determine a similarity between the first data and the second data without executing the action on the first data or the second data.

3. The method of claim 2, wherein the act of executing the action on the first and the second data as part of the first similarity function and the act of executing the second similarity function are both performed in a single execution of a composed function, the composed function comprising a single iteration of the action and other actions comprised by the first or second similarity function.

4. The method of claim 2, wherein the act of executing the second similarity function executes a second action on the first data and the second data and further comprising retaining a result of the second action to provide a second result and using the second result to enable execution of a third similarity function that:

is different from the first similarity function and the second similarity function;

requires execution of the second action on the first data or the second data; and

is performed to determine a similarity between the first data and the second data or fourth data without having to execute the second action on the first data or the second data.

5. The method of claim 2, further comprising executing a third similarity function without executing the action on the first data or the second data, where the third similarity function:

is different than the first similarity function and the second similarity function;

requires execution of the action on the first data and the second data; and

is performed to determine a similarity between the first data and the second data.

6. The method of claim 1, wherein the action tokenizes the first data and the second data.

7. The method of claim 1, further comprising performing the acts of executing and using as part of a deduping process of an extract, transform, and load process.

8. The method of claim 1, wherein and the act of using comprises making the result available as input to an action of the second similarity function or to an action of another iteration of the first similarity function.

9. The method of claim 1, further comprising executing the first similarity function to determine a similarity between the first data and the third data without executing the action on the first data and executing the second similarity function to determine a similarity between the first data and the second data without executing the action on the first. data or the second data.

10. One or more computer-readable media having computer-readable instructions therein that, when executed by a computer, cause the computer to perform acts comprising:

receiving multiple similarity functions performance of which are capable of producing multiple results, the multiple results capable of being merged into a single result with a merge operation; and

composing the multiple similarity functions into a single function capable of producing the single result.

11. The media of claim 10, wherein the act of receiving receives a user-selected similarity function having a user-selected constituent action and the act of composing composes the user-selected constituent action into the single function.

12. The media of claim 10, wherein two or more of the multiple similarity functions comprise a same action and the single function is capable of producing the single result with a single execution of the same action.

13. The media of claim 10, further comprising executing the single function effective to produce the single result with a single pass over the data.

14. The media of claim 10, wherein the act of composing comprises determining what actions are performed by each of the similarity functions and which of those actions are redundant, and ordering the actions that are not redundant.

15. A computer-implemented method comprising:

comparing records of a first window to provide one or more first sets of duplicate records;

comparing records of a second window and at least one duplicate record of each set of the first sets of duplicate records to provide one or more second sets of

duplicate records; and

comparing records of a third window and at least one duplicate record of each set of the second sets of duplicate records to provide one or more third sets of duplicate records.

16. The method of claim 15, wherein each of the first window, the second window, and the third window do not share any records.

17. The method of claim 15, wherein the first, second, and third windows each comprise a first number of records, and further comprising receiving a table of a second number of records and partitioning the table into a third number of windows, where the third number is the second number divided by the first number and rounded up to a nearest integer, and wherein the first window, the second window, and third window are three of the third number of windows partitioning the table.

18. The method of claim 17, further comprising separately comparing records within each of the windows partitioning the table along with a duplicate record if the duplicate record is provided by comparing records of an adjoining window.

19. The method of claim 15, wherein the first window, the second window, and the third window are adjoining windows of a table of records.

20. The method of claim 15, further comprising determining a canonical record for each set of the second sets of duplicate records and wherein the act of comparing records of the third window compares records of the third window and the canonical record for each set of the second sets of duplicate records.