Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Discovering Reliable Dependencies from Data: Hardness and Improved Algorithms

MPG-Autoren
/persons/resource/persons101868

Mandros,  Panagiotis
Databases and Information Systems, MPI for Informatics, Max Planck Society;

/persons/resource/persons188983

Boley,  Mario
Databases and Information Systems, MPI for Informatics, Max Planck Society;

/persons/resource/persons79525

Vreeken,  Jilles
Databases and Information Systems, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1809.05467.pdf
(Preprint), 479KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Mandros, P., Boley, M., & Vreeken, J. (2018). Discovering Reliable Dependencies from Data: Hardness and Improved Algorithms. Retrieved from http://arxiv.org/abs/1809.05467.


Zitierlink: http://hdl.handle.net/21.11116/0000-0002-9EC9-A
Zusammenfassung
The reliable fraction of information is an attractive score for quantifying (functional) dependencies in high-dimensional data. In this paper, we systematically explore the algorithmic implications of using this measure for optimization. We show that the problem is NP-hard, which justifies the usage of worst-case exponential-time as well as heuristic search methods. We then substantially improve the practical performance for both optimization styles by deriving a novel admissible bounding function that has an unbounded potential for additional pruning over the previously proposed one. Finally, we empirically investigate the approximation ratio of the greedy algorithm and show that it produces highly competitive results in a fraction of time needed for complete branch-and-bound style search.