EXAMPLE-DRIVEN DESIGN OF EFFICIENT RECORD MATCHING QUERIES

• US 20080306945A1
• Filed: 06/05/2007
• Published: 12/11/2008
• Est. Priority Date: 06/05/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Ganti, Venkatesh, Kaushik, Shriraghav, Chen, Bee-Chung
• Granted Patent: US 8,046,339 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/24558 Binary matching operations
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries

Abstract

Example-driven creation of record matching queries. The disclosed architecture employs techniques that exploit the availability of positive (or matching) and negative (non-matching) examples to search through this space and suggest an initial record matching query. The record matching task is modeled as that of designing an operator tree obtained by composing a few primitive operators. This ensures that record matching programs be executable efficiently and scalably over large input relations. The architecture joins records across multiple (e.g., two) relations (e.g., R and S). The architecture exploits the monotonicity property of similarity functions for record matching in the relations, in that, any pair of matching records have a higher similarity value than non-matching record pairs on at least one similarity function.

Claims

1. A computer-implemented query system, comprising:

a input component for receiving an example set of matching records and non-matching records between two input relations; and

a modeling component for generating a query based on an operator tree that maximizes identification of the matching records between the two input relations.

2. The system of claim 1, wherein the operator tree is a similarity joins and unions operator tree.

3. The system of claim 2, wherein the similarity joins and unions operator tree is bounded.

4. The system of claim 2, wherein the similarity joins and unions operator tree employs an attribute value transformation operator.

5. The system of claim 1, wherein the modeling component generates the operator tree based on monotonic property of a similarity function.

6. The system of claim 1, further comprising a quality component for quantifying quality of the operator tree based on the matching and non-matching records.

7. The system of claim 6, wherein the quality of the query, as represented by the quality of the operator tree, is based on the non-matching records being less than a user-specified fraction of the matching records in the result.

8. The system of claim 1, wherein the example set is provided manually.

9. The system of claim 1, wherein the operator tree is modified manually.

10. The system of claim 1, wherein the two input relations are joined based on a join predicate that is a conjunction of thresholded similarity values.

11. A computer-implemented method of providing a query, comprising:

receiving an example set of matching records and non-matching records of multiple relations;

generating a bounded operator tree that represents a query which maximizes identification of the matching records between the relations; and

quantifying quality of the operator tree based on monotonicity of the matching and non-matching records.

12. The method of claim 11, wherein the operator tree is a best operator tree derived from finding a maximum hyper-rectangle.

13. The method of claim 12, further comprising finding a best corner as part of finding the maximum hyper-rectangle.

14. The method of claim 12, further comprising building a skyline of negative points as part of finding the maximum hyper-rectangle.

15. The method of claim 12, further comprising adjusting a corner of a candidate rectangle as part of finding the maximum hyper-rectangle.

16. The method of claim 11, wherein the operator tree includes similarity join and union operators.

17. The method of claim 16, wherein the operator tree further includes rename operators.

18. The method of claim 11, further comprising selecting and merging multiple hyper-rectangles to obtain a best hyper-rectangle from which to generate the operator tree.

19. The method of claim 11, further comprising defining a probabilistic bound by a difference in quality of an operator tree generated by a sample of the example set and the quality of the operator tree generated by the example set.

20. A computer-implemented system, comprising:

computer-implemented means for generating a bounded operator tree based on an example set of matching records and non-matching records of multiple relations;

computer-implemented means for quantifying quality of the operator tree based on monotonicity of the matching and non-matching records; and

computer-implemented means for creating a query that maximizes identification of the matching records between the relations.