Patent Document ID: 7516149
Application ID: 10929514
Patent Flag: 1

Claim One:
1. A system to facilitate elimination of fuzzy duplicates which each represent a same real world entity or phenomenon from a dataset R, the system comprising: a system memory; a processor; a dataset obtaining means for obtaining the dataset R comprising multiple tuples from a database, wherein at least some of the tuples are fuzzy duplicates; a computing means for identifying tuples of the dataset R which satisfy a compact set criterion that a set of fuzzy duplicates is a compact set of mutual nearest neighbors in the dataset R such that a set S of tuples from the dataset R is a compact set if for every tuple v in S a distance between tuple v and any other tuple v′ in S is less than a distance between tuple v and any other tuple v″ in R-S wherein the distance is an edit distance and is calculated by any edit distance algorithm, and for identifying tuples of the dataset R which satisfy a sparse neighborhood criterion that a local neighborhood of a set of fuzzy duplicates is sparse, wherein the sparse neighborhood criterion comprises having an aggregated value of neighborhood growth ratios of tuples in S around an individual tuple being less than a growth threshold, wherein the neighborhood growth ratio for an individual tuple is a number of nearest neighbor tuples within a sphere having a radius greater than a distance between every individual tuple in S and its nearest neighbor; a partitioning means for partitioning the dataset R into a plurality of groups, wherein each group comprises tuples which are fuzzy duplicates that denote the same real world entity or phenomenon, and wherein each group comprises tuples which satisfy both the compact set criterion to qualify as a compact set and the sparse neighborhood criterion to qualify as a sparse neighborhood; and a duplicate-elimination means for eliminating all but one of the fuzzy duplicates from a group so that the one of the fuzzy duplicates which remains in the group will represent the real world entity or phenomenon.