We study the problem of listing all closed sets of a closure operator $\sigma$ 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| (T_F +T_+ |E|))$ and space $O(|E| + S_F S_\sigma)$, where $T_F$, $S_F$, $T_\sigma$, and $S_\sigma$ are the time and space complexities of checking membership in $ F$ and computing $\sigma$, 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.
%0 Conference Paper
%1 kdml26
%A Boley, Mario
%A Horvath, Tamas
%A Poigne, Axel
%A Wrobel., Stefan
%B Proceedings of LWA2010 - Workshop-Woche: Lernen, Wissen & Adaptivitaet
%C Kassel, Germany
%D 2010
%E Atzmüller, Martin
%E Benz, Dominik
%E Hotho, Andreas
%E Stumme, Gerd
%K algorithms closed complexity efficient mining pattern room:0446 session:kdml4 workshop:kdml
%T Listing closed sets of strongly accessible set systems with applications to data
%U http://www.kde.cs.uni-kassel.de/conf/lwa10/papers/kdml26.pdf
%X We study the problem of listing all closed sets of a closure operator $\sigma$ 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| (T_F +T_+ |E|))$ and space $O(|E| + S_F S_\sigma)$, where $T_F$, $S_F$, $T_\sigma$, and $S_\sigma$ are the time and space complexities of checking membership in $ F$ and computing $\sigma$, 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.
@inproceedings{kdml26,
abstract = {We study the problem of listing all closed sets of a closure operator $\sigma$ that is a partial function on the power set of some finite ground set $E$, i.e., $\sigma : {\cal F} \to {\cal F}$ with ${\cal F} \subseteq {\cal 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| (T_{\cal F} +T_\sigma + |E|))$ and space $O(|E| + S_{\cal F} S_\sigma)$, where $T_{\cal F}$, $S_{\cal F}$, $T_\sigma$, and $S_\sigma$ are the time and space complexities of checking membership in $\cal F$ and computing $\sigma$, 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.},
added-at = {2010-10-05T14:15:12.000+0200},
address = {Kassel, Germany},
author = {Boley, Mario and Horvath, Tamas and Poigne, Axel and Wrobel., Stefan},
biburl = {https://www.bibsonomy.org/bibtex/275f0dabe405564eb640a8261edfce283/lwa2010},
booktitle = {Proceedings of LWA2010 - Workshop-Woche: Lernen, Wissen {\&} Adaptivitaet},
crossref = {lwa2010},
editor = {Atzmüller, Martin and Benz, Dominik and Hotho, Andreas and Stumme, Gerd},
interhash = {49ca7e8ee8dcb2236232e9653cb576d1},
intrahash = {75f0dabe405564eb640a8261edfce283},
keywords = {algorithms closed complexity efficient mining pattern room:0446 session:kdml4 workshop:kdml},
presentation_end = {2010-10-06 10:45:00},
presentation_start = {2010-10-06 10:22:30},
room = {0446},
session = {kdml4},
timestamp = {2010-10-05T14:15:13.000+0200},
title = {Listing closed sets of strongly accessible set systems with applications to data},
track = {kdml},
url = {http://www.kde.cs.uni-kassel.de/conf/lwa10/papers/kdml26.pdf},
year = 2010
}