Example-driven design of efficient record matching queries

One or more computer-readable storage devices comprising executable instructions that, when executed, cause at least one processor to perform:

• receiving an example set of records from two input relations, the example set comprising:
• pairs of matching records that are labeled as examples of records that are considered a match between the two input relations;
• and
• pairs of non-matching records that are labeled as examples of records that are not considered a match between the two input relations;
• generating an operator tree based on the example set of records from the two input relations, wherein the generating the operator tree comprises:
• mapping the pairs of matching records to positive points in a similarity space based on a similarity function;
• mapping the pairs of non-matching records to negative points in the similarity space based on the similarity function;
• generating one or more similarity joins of the operator tree based on the positive points and the negative points in the similarity space;
• limiting the operator tree to a maximum number of the similarity joins;
• and
• limiting individual similarity joins of the operator tree to a maximum number of similarity function predicates;
• and
• generating a query based on the operator tree, the query identifying individual matching records between the two input relations.

A method comprising steps of:

• receiving an example set of records from two input relations, the example set comprising:
• pairs of matching records that are labeled as examples of records that are considered a match between the two input relations;
• and
• pairs of non-matching records that are labeled as examples of records that are not considered a match between the two input relations;
• and
• generating an operator tree based on the example set of records from the two input relations, wherein the generating the operator tree comprises:
• mapping the pairs of matching records to positive points in a similarity space based on a similarity function;
• mapping the pairs of non-matching records to negative points in the similarity space based on the similarity function;
• generating one or more similarity joins of the operator tree based on the positive points and the negative points in the similarity space;
• limiting the operator tree to a maximum number of the similarity joins;
• and
• limiting individual similarity joins of the operator tree to a maximum number of similarity function predicates;
• and
• generating a query based on the operator tree, the query identifying individual matching records between the two input relations,
• wherein at least one of the steps is performed by one or more computing devices.