RadiusSketch: Massively Distributed Indexing of Time Series - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2017

RadiusSketch: Massively Distributed Indexing of Time Series

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.
Fichier principal
Vignette du fichier
ParSketch__DSAA_.pdf (1.12 Mo) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01620154 , version 1 (20-10-2017)

Identifiers

Cite

Djamel-Edine Edine Yagoubi, Reza Akbarinia, Florent Masseglia, Dennis Shasha. RadiusSketch: Massively Distributed Indexing of Time Series. IEEE International Conference on Data Science and Advanced Analytics (DSAA 2017), Oct 2017, Tokyo, Japan. pp.262-271, ⟨10.1109/DSAA.2017.49⟩. ⟨lirmm-01620154⟩
231 View
824 Download

Altmetric

Share

More