Atomic Patterns for Efficient Computation with Pattern Structures
摘要
Pattern Structures is a framework in FCA allowing objects to have complex descriptions, only requiring that the set of descriptions forms a complete meet-semi-lattice. However, some particular descriptions or patterns, such as subgraphs and subsequences, do not necessarily ensure that every pair of descriptions has a unique infimum and ask for additional operations, e.g., antichain completion. Moreover, meet-based approaches struggle to generate non-trivial implications for complex data since, in general, they only output closed descriptions. For overcoming such limitations, we introduce in this paper an alternative view of pattern structures based on the join operation and the so-called “atomic patterns”. Such atomic patterns correspond to join-irreducible descriptions in the join-semi-lattice of all possible descriptions. They enable an efficient traversal of the description space and the computation of closures, minimal generators, pseudo-intents, implications among others, while showing very good computational performance.