@article{SchirmerPapenbrockKoumarelasetal.2020,
  author    = {Schirmer, Philipp and Papenbrock, Thorsten and Koumarelas, Ioannis and Naumann, Felix},
  title     = {Efficient discovery of matching dependencies},
  series = {ACM transactions on database systems : TODS},
  volume    = {45},
  journal   = {ACM transactions on database systems : TODS},
  number    = {3},
  publisher = {Association for Computing Machinery},
  address   = {New York},
  issn      = {0362-5915},
  doi       = {10.1145/3392778},
  pages     = {33},
  year      = {2020},
  abstract  = {Matching dependencies (MDs) are data profiling results that are often used for data integration, data cleaning, and entity matching. They are a generalization of functional dependencies (FDs) matching similar rather than same elements. As their discovery is very difficult, existing profiling algorithms find either only small subsets of all MDs or their scope is limited to only small datasets. We focus on the efficient discovery of all interesting MDs in real-world datasets. For this purpose, we propose HyMD, a novel MD discovery algorithm that finds all minimal, non-trivial MDs within given similarity boundaries. The algorithm extracts the exact similarity thresholds for the individual MDs from the data instead of using predefined similarity thresholds. For this reason, it is the first approach to solve the MD discovery problem in an exact and truly complete way. If needed, the algorithm can, however, enforce certain properties on the reported MDs, such as disjointness and minimum support, to focus the discovery on such results that are actually required by downstream use cases. HyMD is technically a hybrid approach that combines the two most popular dependency discovery strategies in related work: lattice traversal and inference from record pairs. Despite the additional effort of finding exact similarity thresholds for all MD candidates, the algorithm is still able to efficiently process large datasets, e.g., datasets larger than 3 GB.},
  language  = {en}
}
@article{DraisbachChristenNaumann2019,
  author    = {Draisbach, Uwe and Christen, Peter and Naumann, Felix},
  title     = {Transforming pairwise duplicates to entity clusters for high-quality duplicate detection},
  series = {ACM Journal of Data and Information Quality},
  volume    = {12},
  journal   = {ACM Journal of Data and Information Quality},
  number    = {1},
  publisher = {Association for Computing Machinery},
  address   = {New York},
  issn      = {1936-1955},
  doi       = {10.1145/3352591},
  pages     = {1 -- 30},
  year      = {2019},
  abstract  = {Duplicate detection algorithms produce clusters of database records, each cluster representing a single real-world entity. As most of these algorithms use pairwise comparisons, the resulting (transitive) clusters can be inconsistent: Not all records within a cluster are sufficiently similar to be classified as duplicate. Thus, one of many subsequent clustering algorithms can further improve the result. <br /> We explain in detail, compare, and evaluate many of these algorithms and introduce three new clustering algorithms in the specific context of duplicate detection. Two of our three new algorithms use the structure of the input graph to create consistent clusters. Our third algorithm, and many other clustering algorithms, focus on the edge weights, instead. For evaluation, in contrast to related work, we experiment on true real-world datasets, and in addition examine in great detail various pair-selection strategies used in practice. While no overall winner emerges, we are able to identify best approaches for different situations. In scenarios with larger clusters, our proposed algorithm, Extended Maximum Clique Clustering (EMCC), and Markov Clustering show the best results. EMCC especially outperforms Markov Clustering regarding the precision of the results and additionally has the advantage that it can also be used in scenarios where edge weights are not available.},
  language  = {en}
}