On Indexing Error-Tolerant Set Containment - Agrawal, Parag; Arasu, Arvind; Kaushik, Raghav (Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2010)
Prior work has identiﬁed set based comparisons as a useful primitive for supporting a wide variety of similarity functions in record matching. Accordingly, various techniques have been proposed to improve the performance of set similarity lookups. However, this body of work focuses almost exclusively on symmetric notions of set similarity. In this paper, we study the indexing problem for the asymmetric Jaccard containment similarity function that is an error-tolerant variation of set containment. We enhance this similarity function to also account for string transformations that reﬂect synonyms such as “Bob” and “Robert” referring to the same ﬁrst name. We propose an index structure that builds inverted lists on carefully chosen token-sets and a lookup algorithm using our index that is sensitive to the output size of the query. Our experiments over real life data sets show the beneﬁts of our techniques. To our knowledge, this is the ﬁrst paper that studies the indexing problem for Jaccard containment in the presence of string transformations.