RadiusSketch: Massively Distributed Indexing of Time Series

Djamel-Edine Yagoubi 1 Reza Akbarinia 1 Florent Masseglia 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 : Performing similarity queries on hundreds of millions of time series is a challenge requiring both efficient indexing techniques and parallelization. We propose a sketch/random projection-based approach that scales nearly linearly in parallel environments, and provides high quality answers. We illustrate the performance of our approach, called RadiusSketch, on real and synthetic datasets of up to 1 Terabytes and 500 million time series. The sketch method, as we have implemented, is superior in both quality and response time compared with the state of the art approach, iSAX2+. Already, in the sequential case it improves recall and precision by a factor of two, while giving shorter response times. In a parallel environment with 32 processors, on both real and synthetic data, our parallel approach improves by a factor of up to 100 in index time construction and up to 15 in query answering time. Finally, our data structure makes use of idle computing time to improve the recall and precision yet further.
Type de document :
Communication dans un congrès
DSAA 2017: IEEE International Conference on Data Science and Advanced Analytics, Oct 2017, Tokyo, Japan. pp.1-10, 2017
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01620154
Contributeur : Reza Akbarinia <>
Soumis le : vendredi 20 octobre 2017 - 11:14:25
Dernière modification le : jeudi 11 janvier 2018 - 17:01:55

Fichier

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

Identifiants

  • HAL Id : lirmm-01620154, version 1

Citation

Djamel-Edine Yagoubi, Reza Akbarinia, Florent Masseglia, Dennis Shasha. RadiusSketch: Massively Distributed Indexing of Time Series. DSAA 2017: IEEE International Conference on Data Science and Advanced Analytics, Oct 2017, Tokyo, Japan. pp.1-10, 2017. 〈lirmm-01620154〉

Partager

Métriques

Consultations de la notice

106

Téléchargements de fichiers

98