Identifying sets of items that are equivalent to one another is a problem common to many fields. Systems addressing this generally have at their core a function s(di, dj ) for computing the similarity between pairs of records di, dj . The output of s() can be interpreted as a weighted graph where edges indicate the likelihood of two records matching. Partitioning this graph into equivalence classes is non-trivial due to the presence of inconsistencies and imperfections in s().
