Efficient Taxonomic Similarity Joins with Adaptive Overlap Constraint
This work addresses the problem of improving similarity join quality for data integration tasks by leveraging semantic relations, though it is incremental as it builds on existing prefix filtering frameworks.
The paper tackles the problem of similarity joins by incorporating taxonomy knowledge to define a semantic similarity measure, enabling the identification of semantically similar records between datasets. The result is a highly efficient and scalable algorithm that outperforms state-of-the-art methods by a large margin.
A similarity join aims to find all similar pairs between two collections of records. Established approaches usually deal with synthetic differences like typos and abbreviations, but neglect the semantic relations between words. Such relations, however, are helpful for obtaining high-quality joining results. In this paper, we leverage the taxonomy knowledge (i.e., a set of IS-A hierarchical relations) to define a similarity measure which finds semantic-similar records from two datasets. Based on this measure, we develop a similarity join algorithm with prefix filtering framework to prune away irrelevant pairs effectively. Our technical contribution here is an algorithm that judiciously selects critical parameters in a prefix filter to maximise its filtering power, supported by an estimation technique and Monte Carlo simulation process. Empirical experiments show that our proposed methods exhibit high efficiency and scalability, outperforming the state-of-art by a large margin.