Robust detector of fuzzy duplicates

• US 20060053129A1
• Filed: 08/30/2004
• Published: 03/09/2006
• Est. Priority Date: 08/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Ganti, Venkatesh, Motwani, Rajeev
• Granted Patent: US 7,516,149 B2
• 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
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting
• 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
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

At least one implementation, described herein, detects fuzzy duplicates and eliminates such duplicates. Fuzzy duplicates are multiple, seemingly distinct tuples (i.e., records) in a database that represent the same real-world entity or phenomenon.

Claims

1. One or more processor-readable program media having processor-executable instructions that, when executed by a processor, perform acts comprising:

obtaining a dataset comprising multiple tuples from a database;

for each of the multiple tuples of the dataset, computing one or more nearest neighbor tuples in the dataset;

defining multiple disjoint partitions of multiple tuples, wherein tuples in each partition comprise fuzzy duplicates of one another, such that each fuzzy duplicate tuple in a partition represents a common real world entity or phenomenon.

2. One or more processor-readable program media as recited in claim 1 further comprising eliminating duplicates within the multiple partitions of multiple fuzzy duplicate tuples so that each of such partition is left with one, unduplicated tuple.

3. One or more processor-readable program media as recited in claim 1, wherein the computing further comprises computing a defined number of nearest neighbor tuples in the dataset.

4. One or more processor-readable program media as recited in claim 1, wherein the computing further comprises:

computing a defined number of nearest neighbor tuples in the dataset and defining a set of defined number of nearest neighbor tuples for each tuple to be a “

neighborhood”

;

computing a “

neighborhood growth ratio”

for each neighborhood.

5. One or more processor-readable program media as recited in claim 1, wherein the computing further comprises looking up nearest neighbors via an index of the tuples in the dataset.

6. One or more processor-readable program media as recited in claim 1, wherein the defining further comprises defining multiple partitions of multiple tuples based upon each partition being a “

compact set” and

a “

sparse neighborhood.”

7. One or more processor-readable program media as recited in claim 1, wherein the defining further comprises defining multiple partitions of multiple tuples based upon each partition being a “

compact set,”

a “

sparse neighborhood,” and

a “

small cardinality.”

8. One or more processor-readable program media as recited in claim 1, wherein the tuples in each partition further comprise exact duplicates of one another.

9. A fuzzy duplicate elimination system comprising:

a dataset obtaining means for obtaining a dataset comprising multiple tuples from a database;

a computing means for computing one or more nearest neighbor tuples in the dataset for each of the multiple tuples of the dataset;

a partitioning means for defining multiple disjoint partitions of multiple tuples, wherein seemingly distinct tuples in each partition comprise fuzzy duplicates of one another, such that each fuzzy duplicate tuple in a partition represents a common real world entity or phenomenon;

a duplicate-elimination means for eliminating duplicates of multiple fuzzy duplicate tuples within the multiple partitions so that each of such partitions is left with one, unduplicated tuple.

10. A system as recited in claim 9, wherein the tuples in each partition further comprise exact duplicates of one another.

11. A system as recited in claim 9, wherein the computing means is for computing a defined number of nearest neighbor tuples in the dataset.

12. A system as recited in claim 9, wherein the computing means is also for:

computing a defined number of nearest neighbor tuples in the dataset and defining a set of defined number of nearest neighbor tuples for each tuple to be a “

neighborhood”

;

computing a “

neighborhood growth ratio”

for each neighborhood.

13. A system as recited in claim 9, wherein the computing means is also for looking up nearest neighbors via an index of the tuples in the dataset.

14. A system as recited in claim 9, wherein the partitioning means is for defining multiple partitions of multiple tuples based upon each partition being a “

compact set” and

a “

sparse neighborhood.”

15. A system as recited in claim 9, wherein the partitioning means is for defining multiple partitions of multiple tuples based upon each partition being a “

compact set,”

a “

sparse neighborhood,” and

a “

small cardinality.”

16. A method for eliminating fuzzy duplicate tuples in a dataset, the method comprising:

for each of multiple tuples in a dataset, computing one or more nearest neighbor tuples;

delimitating delimiting multiple disjoint partitions of multiple tuples, wherein seemingly distinct tuples in each partition comprise fuzzy duplicates of one another, such that each fuzzy duplicate tuple in a partition represents a common real world entity or phenomenon;

eliminating duplicates within the multiple partitions of multiple fuzzy duplicate tuples so that each of such partitions is left with one, unduplicated tuple.

17. A system as recited in claim 16, wherein the computing comprises computing a defined number of nearest neighbor tuples in the dataset.

18. A method as recited in claim 16, wherein the computing comprises:

computing a defined number of nearest neighbor tuples in the dataset and defining a set of defined number of nearest neighbor tuples for each tuple to be a “

neighborhood”

;

computing a “

neighborhood growth ratio”

for each neighborhood.

19. A method as recited in claim 16, wherein the computing comprises looking up nearest neighbors via an index of the tuples in the dataset.

20. A method as recited in claim 16, wherein the delimiting comprises delimiting multiple partitions of multiple tuples based upon each partition being a “

compact set” and

a “

sparse neighborhood.”

21. A method as recited in claim 16, wherein the delimiting comprises delimiting multiple partitions of multiple tuples based upon each partition being a “

compact set,”

a “

sparse neighborhood,” and

a “

small cardinality.”