# US 2008/0306945 A1 · Example-driven design of efficient record matching queries

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0306945 A1
- Document ID: US20080306945A1
- Status: Published application
- Kind: A1
- Application number: 11/758,202
- Filed: 2007-06-05
- Published: 2008-12-11
- Earliest claimed: 2007-06-05
- Assignees: Microsoft Corporation
- Inventors: Surajit Chaudhuri; Bee-Chung Chen; Venkatesh Ganti; Shriraghav Kaushik
- Web page: https://patentgrep.com/patent/US20080306945A1

## CPC

- G06F 16/24558: {Binary matching operations}
- G06F 16/2458: Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 2)

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

### Claim 5 (depends on 1)

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

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 1)

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

### Claim 9 (depends on 1)

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

### Claim 10 (depends on 1)

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.

### Claim 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.

### Claim 12 (depends on 11)

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

### Claim 13 (depends on 12)

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

### Claim 14 (depends on 12)

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

### Claim 15 (depends on 12)

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

### Claim 16 (depends on 11)

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

### Claim 17 (depends on 16)

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

### Claim 18 (depends on 11)

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.

### Claim 19 (depends on 11)

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.

### Claim 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.
