Primitive operator for similarity joins in data cleaning

• US 20070192342A1
• Filed: 02/10/2006
• Published: 08/16/2007
• Est. Priority Date: 02/10/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Ganti, Venkatesh, Shriraghav, Kaushik
• Granted Patent: US 7,406,479 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A set similarity join system and method are provided. The system can be employed to facilitate data cleaning based on similarities through the identification of “close” tuples (e.g., records and/or rows). “Closeness” can be is evaluated using a similarity function(s) chosen to suit the domain and/or application. Thus, the system facilitates generic domain-independent data cleansing. The system can be employed with a foundational primitive, the set similarity join (SSJoin) operator, which can be used as a building block to implement a broad variety of notions of similarity (e.g., edit similarity, Jaccard similarity, generalized edit similarity, hamming distance, soundex, etc.) as well as similarity based on co-occurrences. The SSJoin operator can exploit the observation that set overlap can be used effectively to support a variety of similarity functions. The SSJoin operator compares values based on “sets” associated with (or explicitly constructed for) each one of them.

Claims

1. A set similarity join system, comprising:

a mapping component that maps strings to sets; and

,

a set similarity join component that provides a similarity join output based, at least in part, upon a set overlap between the sets.

2. The system of claim 1, the mapping component maps a first string to a first set and a second string to a second set.

3. The system of claim 2, the similarity join component provides a similarity join output based, at least in part, upon a set overlap between the first set and the second set.

4. The system of claim 2, the mapping component maps strings to sets based on q-grams.

5. The system of claim 1 invoked by an SSJoin operator, the SSJoin operator based, at least in part, upon R SSJoin_A^pred S.

where R and S are relations,

pred is a predicate ˆ

_i{Overlap_B(a_r;

a_s)≧

e_i},

e_i is an expression involving only constants and columns from either R.A or S.A,

R(A, B) and S(A, B) where A and B are subsets of columns, and,

Each distinct value a_r∈

R.A defines a group, which is the subset of all tuples in R where R.A=a_r.

6. The system of claim 5, the SSJoin operator returns pairs of distinct values <

R.A, S.A>

if the overlap of the corresponding groups of R[B] and S[B] values is above a threshold.

7. The system of claim 1, set overlap is determined based, at least in part, upon a function.

8. The system of claim 7, the function is based on at least one of edit similarity, Jaccard similarity, generalized edit similarity, Hamming distance and soundex.

9. The system of claim 7, the function is the based on edit distance between a first set σ

₁ and a second set σ

₂ based, at least in part upon;

$\mathrm{ES}<br><br>\left({\mathrm{\sigma <br><br>}}_1,{\mathrm{\sigma <br><br>}}_2\right)=1.0-\frac{\mathrm{ED}<br><br>\left({\mathrm{\sigma <br><br>}}_1,{\mathrm{\sigma <br><br>}}_2\right)}{\max <br><br>\left(<br><br>{\mathrm{\sigma <br><br>}}_1<br><br>,<br><br>{\mathrm{\sigma <br><br>}}_2<br><br>\right)}.$

where ES denotes edit similarity; and

,

ED denotes edit distance.

10. The system of claim 7, the function is on Jaccard containment, Jaccard containment based, at least in part, upon:

$\mathrm{JC}<br><br>\left(s_1,s_2\right)=\frac{\mathrm{wt}<br><br>\left(s_1\bigcap <br><br>s_2\right)}{\mathrm{wt}<br><br>\left(s_1\right)}.$

where s₁ is a first set,

s₂ is a second set and,

JC is a Jaccard containment function.

11. The system of claim 7, the function is based on Jaccard resemblance, Jaccard resemblance is based, at least in part, upon:

$\mathrm{JR}<br><br>\left(s_1,s_2\right)=\frac{\mathrm{wt}<br><br>\left(s_1\bigcap <br><br>s_2\right)}{\mathrm{wt}<br><br>\left(s_1\bigcup <br><br>s_2\right)}$

where s₁ is a first set,

s₂ is a second set and,

JR is a Jaccard resemblance function.

12. The system of claim 7, the function is based on generalized edit similarity, generalized edit similarity is based, at least in part, upon:

$\mathrm{GES}<br><br>\left({\mathrm{\sigma <br><br>}}_1,{\mathrm{\sigma <br><br>}}_2\right)=1.0-\left(\frac{\mathrm{tc}<br><br>\left({\mathrm{\sigma <br><br>}}_1,{\mathrm{\sigma <br><br>}}_2\right)}{\mathrm{wt}<br><br>\left(\mathrm{Set}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left({\mathrm{\sigma <br><br>}}_1\right)\right)},1.0\right)$

where GES is the generalized edit similarity function,

σ

₁ is a first string,

σ

₂ is a second string,

tc is a total cost function, and,

wt is a weight function.

13. The system of claim 7, the function is based, at least in part, upon co-occurrence.

14. The system of claim 7, the function is based, at least in part, upon soft functional dependencies.

15. The system of claim 1, the set similarity join component employs a prefix-filter to the sets to determine set overlaps between the sets.

16. The system of claim 1, the similarity join output is based, at least in part, upon a threshold level of similarity.

17. A set similarity join method, comprising:

mapping strings to sets;

determining set overlap of the sets; and

,

providing a similarity join output based on the set overlap of the sets.

18. The method of claim 17, set overlap is determined based, at least in part, upon a function.

19. A set similarity join system, comprising:

means for mapping strings to sets; and

,

means for providing a similarity join output based, at least in part, upon a set overlap between the sets.

20. The system of claim 19, set overlap is determined based, at least in part, upon a function.