Pattern Mining Days 8-9 July 2013 in Grenoble

Debugging Embedded Multimedia Application Execution Traces through Periodic Pattern Mining

• President: Frédéric Pétrot, Pr, Grenoble INP
• Reviewer: Hiroki Arimura, Pr, Hokkaido University, Japan
• Reviewer: Gilles Sassatelli, DR CNRS, LIRMM
• Examiner: Jean-François Boulicaut, Pr, INSA Lyon
• Examiner: Takashi Washio, Osaka University, Japan
• Advisor: Jean-François Méhaut, Pr, Université Joseph Fourier
• Co-advisor: Alexandre Termier, MCF, Université Joseph Fourier
• Co-advisor: Miguel Santana, STMicroelectronics

Increasing complexity in both the software and the underlying hardware, and ever tighter time-to-market pressures are some of the key challenges faced when designing multimedia embedded systems. Optimizing software debugging and validation phases can help to reduce development time significantly. A powerful tool used extensively when debugging embedded systems is the analysis of execution traces. However, evolution in embedded system tracing techniques leads to execution traces with a huge amount of information, making manual trace analysis unmanageable. In such situations, pattern mining techniques can help by automatically discovering interesting patterns in large amounts of data. Concretely, in this thesis, we are interested in discovering periodic behaviors in multimedia applications. Therefore, the contributions of this thesis are focused on the definition of periodic pattern mining techniques for the analysis of multimedia applications execution traces.

Regarding periodic pattern mining contributions, we propose a definition of periodic pattern adapted to the characteristics of concurrent software. We then propose a condensed representation of the set of frequent periodic patterns, called Core Periodic Concepts (CPC), by adopting an approach originated in triadic concept approach. Moreover, we define certain connectivity properties of these patterns that allow us to implement an evercient CPC mining algorithm, called PerMiner. Then, we perform a thorough analysis to show the everciency and scalability of PerMiner algorithm. We show that PerMiner algorithm is at least two orders of magnitude faster than the state of the art. Moreover, we evaluate the everciency of PerMiner algorithm over a real multimedia application trace and also present the speedup achieved by a parallel version of the algorithm.

Then, regarding embedded systems contributions, we propose a first step towards a methodology which aims at giving the first guidelines of how to use our approach in the analysis of multimedia applications execution traces. Besides, we propose several ways of preprocessing execution traces and a competitors finder tool to postprocess the mining results. Moreover, we present a CPC visualization tool, called CPCViewer, that facilitates the analysis of a set of CPCs. Finally, we show that our approach can help in debugging multimedia applications through the study of two use cases over real multimedia application execution traces.

Pattern mining rock: more, faster, better

• President: Claudia Roncancio, Pr, Grenoble INP
• Reviewer: Hiroki Arimura, Pr, Hokkaido University, Japan
• Reviewer: Jean-François Boulicaut, Pr, INSA Lyon
• Reviewer: Mohammed J. Zaki, Rensselaer Polytechnic Institute, NY, USA
• Examiner: Marie-Odile Cordier, Pr, Université Rennes 1
• Examiner: Jean-François Méhaut, Pr, Université Joseph Fourier
• Examiner: Marie-Christine Rousset, Pr, Université Joseph Fourier
• Examiner: Takashi Washio, Osaka University, Japan

Pattern mining is the area of data mining concerned with finding regularities in data. In this defense I will present my contributions to this domain along three axes:

1. The domain is young, and there are still some kinds of regularities that data analysts would like to discover in data but that are not handled. We contributed two new pattern definitions extending the reach of data analysis by pattern mining: gradual patterns and periodic patterns with unrestricted gaps. We also proposed ParaMiner, a pioneering algorithm for generic pattern mining, allowing practitioners to directly specify the patterns they are interested in.
2. Pattern mining is extremely demanding on computational resources. In order to reduce the mining time, we studied how to exploit the parallelism of multicore processors. Our results show that some well established techniques in pattern mining are ill-adapted for parallelism, and propose solutions.
3. Our ultimate goal is to make pattern mining easier to use by data analysts. There is a lot to do in this area, as currently they are presented with unusable lists of millions of patterns. We will present our first results in the context of mining execution traces of processors.

• Alexandre Termier, Université Joseph Fourier
• Takashi Washio, Osaka University, Japan

• 9:00 - 9:10 Opening (Alexandre Termier & Takashi Washio)
• 9:10 - 10:10 Hiroki Arimura, (title TBA)
• 10:10 - 10:40 – coffee break --
• 10:40 - 11:40 Henri Soldano, "Abstract closed motifs : a latticial view on motifs and abstraction"
• 11:40 - 13:00 – lunch break --
• 13:00 - 14:00 Takashi Washio + Christiane Kamdem Kengne, "A Packing Problem: Efficient Rewriting of Large Multimedia Execution Traces"
• 14:00 - 15:00 Thomas Guyet, "Mining frequent sequential patterns from traces of dynamical systems"
• 15:00 - 15:30 – coffee break --
• 15:30 - 16:30 Martin Kirchgessner + Vincent Leroy, "Mining frequent patterns for the long tail"
• 16:30 - 17:00 Concluding