Listing closed sets of strongly accessible set systems with applications to data mining

Mario Boley, Tamás Horváth, Axel Poigné, Stefan Wrobel

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We study the problem of listing all closed sets of a closure operator σ that is a partial
function on the power set of some finite ground set E, i.e., σ : F → F with F ⊆ P (E). A very simple divide-and-conquer algorithm is analyzed that correctly solves this problem if and only if the domain of the closure operator is a strongly accessible set system. Strong accessibility is a strict relaxation of greedoids as well as of independence systems. This algorithm turns out to have delay O (|E|(TF + Tσ + |E|)) and space O (|E| + SF + Sσ ), where TF , SF , Tσ , and Sσ are the time and space complexities of checking membership in F and computing σ, respectively. In contrast, we show that the problem becomes intractable for accessible set systems. We relate our results to the data mining problem of listing all support-closed patterns of a dataset and show that there is a corresponding closure operator for all datasets if and only if the set system satisfies a certain confluence property.
Original languageEnglish
Pages (from-to)691-700
JournalTheoretical Computer Science
Volume411
Issue number3
Publication statusPublished - 2010
Externally publishedYes

Cite this