Hasso-Plattner-Institut
Prof. Dr. Felix Naumann
 

29.08.2014

2 full papers accepted at CIKM

Estimating the Number and Sizes of Fuzzy-Duplicate Clusters

Arvid Heise, Gjergji Kasneci, and Felix Naumann

Abstract.Duplicates in a dataset are multiple representations of the same real-world entity and constitute a major data quality problem. This paper investigates the problem of estimating the number and sizes of duplicate record clusters in advance and describes a sampling-based method for solving this problem. In extensive experiments, on multiple datasets, we show that the proposed method reliably estimates the number of duplicate clusters, while being highly efficient.

Our method can be used a) to measure the dirtiness of a dataset, b) to assess the quality of duplicate detection configurations, such as similarity measures, and c) to gather approximate statistics about the true number of entities represented in the dataset.

 

DFD: Efficient Functional Dependency Discovery

Ziawasch Abedjan, Patrick Schulze, and Felix Naumann

Abstract.The discovery of functional dependencies in a dataset is of great importance for database redesign, anomaly detection and data cleansing applications. However, as the nature of the problem is exponential in the number of attributes none of the existing approaches can be applied on large datasets. We present a new algorithm DFD for discovering all functional dependencies in a dataset following a depth-first traversal strategy of the attribute lattice that combines aggressive pruning and efficient result verification. Our approach is able to scale far beyond existing algorithms for up to 7.5 million tuples, and is up to three orders of magnitude faster than existing approaches on smaller datasets.