## G. Cormode, L. Golab, F. Korn, A. McGregor, D. Srivastava, and X. Zhang.
Estimating the confidence of conditional functional dependencies.
In *ACM SIGMOD International Conference on Management of Data
(SIGMOD)*, 2009.

Conditional functional dependencies (CFDs) have recently been proposed as
extensions of classical functional dependencies that apply to a certain
subset of the relation, as specified by a *pattern tableau*.
Calculating the support and confidence of a CFD (i.e., the size of the
applicable subset and the extent to which it satisfies the CFD)
gives valuable information about data semantics and data quality.
While computing the support is easier, computing the confidence
exactly is expensive if the relation is large, and estimating it from a
random sample of the relation is unreliable unless the sample is large.
We study how to efficiently estimate the confidence of a CFD
with a small number of passes (one or two) over the input using small space.
Our solutions are based on a variety of sampling and sketching techniques,
and apply when the pattern tableau is known in advance, and also the harder
case when this is given after the data have been seen.
We analyze our algorithms, and show that they can guarantee
a small additive error; we also show that relative errors guarantees are not possible.
We demonstrate the power of these methods empirically, with a detailed study over
a mixture of real and synthetic data.
These experiments show that it is possible to estimates the CFD confidence
very accurately with summaries which are much smaller than the size of the data they represent.

[ bib |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*