Skip to Main content Skip to Navigation
Conference papers

RadiusSketch: Massively Distributed Indexing of Time Series

Djamel-Edine 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Reza Akbarinia Connect in order to contact the contributor
Submitted on : Friday, October 20, 2017 - 11:14:25 AM
Last modification on : Friday, August 5, 2022 - 3:03:28 PM
Long-term archiving on: : Sunday, January 21, 2018 - 1:07:55 PM


Files produced by the author(s)



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⟩



Record views


Files downloads