ParCorr: efficient parallel methods to identify similar time series pairs across sliding windows

Djamel Edine Yagoubi 1 Reza Akbarinia 1 Boyan Kolev 1 Oleksandra Levchenko 1 Florent Masseglia 1 Patrick Valduriez 1 Dennis Shasha 2
1 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Consider the problem of finding the highly correlated pairs of time series over a time window and then sliding that window to find the highly correlated pairs over successive co-temporous windows such that each successive window starts only a little time after the previous window. Doing this efficiently and in parallel could help in applications such as sensor fusion, financial trading, or communications network monitoring, to name a few. We have developed a parallel incremental random vector/sketching approach to this problem (as explained in section 4) and compared it with the state-of-the-art nearest neighbor method iSAX [7]. Whereas iSAX achieves 100% recall and precision for Euclidean distance, the sketching approach is, empirically, at least 10 times faster and achieves 95% recall and 100% precision on real and simulated data. For many applications this speedup is worth the minor reduction in recall. Our method scales up to 100 million time series and scales linearly in its expensive steps (but quadratic in the less expensive ones).
Type de document :
Article dans une revue
Data Mining and Knowledge Discovery, Springer, 2018, 32 (5), pp.1481-1507. 〈10.1007/s10618-018-0580-z〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01886794
Contributeur : Reza Akbarinia <>
Soumis le : mercredi 3 octobre 2018 - 11:13:28
Dernière modification le : mercredi 21 novembre 2018 - 19:48:06

Fichier

ParCorr__DMKD2018.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Djamel Edine Yagoubi, Reza Akbarinia, Boyan Kolev, Oleksandra Levchenko, Florent Masseglia, et al.. ParCorr: efficient parallel methods to identify similar time series pairs across sliding windows. Data Mining and Knowledge Discovery, Springer, 2018, 32 (5), pp.1481-1507. 〈10.1007/s10618-018-0580-z〉. 〈lirmm-01886794〉

Partager

Métriques

Consultations de la notice

45

Téléchargements de fichiers

34