Efficient Search for Strong Partial Determinations

All Contents

Our work offers both a solution to the problem of finding functional dependencies that are distorted by noise and to the open problem of efficiently finding strong (i.e., highly compressive) partial determinations per se. Briefly, we introduce a restricted form of search for partial determinations which is based on functional dependencies. Focusing attention on solely partial determinations derivable from overfitting functional dependencies enables efficient search for strong partial determinations. Furthermore, we generalize the compression-based measure for evaluating partial determinations to n-valued attributes. Applications to real-world data suggest that the restricted search indeed retrieves a subset of strong partial determinations in much shorter runtimes, thus showing the feasibility and usefulness of our approach.