講演者：Jean-Marc.Petit
所属：INSA de Lyon, France
日時：5/15（水） 13:00-14:30
場所：W2号館10階の第1019室
講演タイトル：Restructuring Maximal Pattern Mining Problems
講演概要：
The framework of Mannila and Toivonen \cite{MT97} classifies pattern mining problems that are (isomorphically) equivalent to 
frequent itemset mining (FIM). Moreover, the notion of \emph{dualization} turns out to be crucial to characterize the complexity of maximal patterns mining problems. 
Nevertheless, many pattern mining problems cannot benefit from this framework since the isomorphism requirement is too restrictive for
many patterns such as sequences, episodes or graphs to mention a few.
In this setting, our ambition is to extend their framework to take into account such complex patterns and studying their complexity.
First, we identify and classify pattern structures, which are not boolean lattices, for which the dualization problem remains quasi-polynomial. 
We introduce \emph{convex embedding} and \emph{poset reduction} as key notions to obtain a new classification of pattern mining problems.
Second, we point out how to adapt the seminal \textsc{Dualize \& Advance} algorithm for these classes.
Last but not least, we point out how known instances of complex pattern mining problems, including sequences and conjunctive queries, fit into our framework.