Inproceedings,

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

, , , and .
Proceedings of LWA2010 - Workshop-Woche: Lernen, Wissen & Adaptivitaet, Kassel, Germany, (2010)

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., $: 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.

Tags

Users

  • @lwa2010
  • @sdo

Comments and Reviews