offres d'emploi formations actualités contact accès annuaire intranet
Séminaires >

Accélération de l’appariement élastique pour la complétion de séquences temporelles dans de grands volumes de données

Bienvenu Fassinut-Mombot, LISIC

jeudi 16 octobre 2014 à 13h00

salle B014


L’appariement élastique, appelé également alignement dynamique temporel, ou Dynamic time warping (DTW) est l’une des plus robustes mesures de distance utilisée dans la recherche par similarité de séquences dans de grands volumes de données. En effet, la DTW s’affranchit des problèmes de déphasage, de distorsion ou d’amplification qui sont très courants dans les séries temporelles ainsi que la difficulté de mise à l’échelle de grands volumes de données à traiter limitant souvent leur exploration à quelques millions d’objets. Cependant, la DTW souffre de quelques limitations dont le coût computationnel en est le principal goulot d’étranglement. Nous présentons ici un moyen de limiter le nombre de calculs de DTW, inspiré des travaux de Koegh et al. La méthode vérifie d’une part, si la valeur de la dissimilarité calculée et normalisée excède une certaine tolérance, et si c’est le cas, la séquence candidate de la base sera abandonnée et sera exclue du calcul exacte de la DTW. La valeur de la tolérance peut être mise à jour à la dernière valeur de la dissimilarité rejetée. D’autre part, la méthode exploite naturellement le parallélisme intrinsèque des processeurs multi-coeurs en implémentant des buffers circulaires pour lire et/ou stocker des données courantes. L’application de cette approche a été mis en œuvre dans le cadre de la complétion de données manquantes issues de la station MAREL Carnot, installée dans la rade de Boulogne-sur-Mer.