New Publication at EDBT 2021!

27—May—2021, by Giorgos Chatzigeorgakidis

We are delighted to announce that our paper titled Twin Subsequence Search in Time Series was recently published at the 24th International Conference on Extending Database Technology (EDBT) 2021!

The paper addresses the problem of twin subsequence search in time series using Chebyshev distance, an alternative, “stricter” distance measure for time series. The Chebyshev distance between two time series is calculated by considering the maximum difference of their values across their entire duration. We call two subsequences twins with respect to a distance threshold, if their Chebyshev distance is not greater than it.

Take for example the image shown below, which exemplifies the intuition behind matches obtained with Chebyshev distance compared to those with Euclidean, for two different queries. Assume a query sequence 𝑄 and two matches, 𝑇 and 𝑇’ , obtained under Chebyshev and Euclidean distance, respectively. As shown, 𝑇 closely matches the query in all timestamps. Instead, 𝑇’ either lacks a spike that is present in the query (leftmost plot in the image) or exhibits one that is not present in the query (rightmost plot in the image).

To calculate twin subsequence search queries efficiently, we introduce TS-Index, a novel index tailored to this problem. TS-Index is a tree-based index tailored to twin subsequence search, which utilizes appropriate bounds in its nodes to prune the search space. Our paper includes a thorough experimental evaluation, which compares our approaches with baseline and state-of-the-art methods against real time series datasets, and demonstrates that TS-Index can retrieve twin subsequences much faster under various query conditions.

Our approach will be extended to support twin subsequence search queries on geolocated time series and will be integrated into the Topio platform as a Value Added Service. It will be used on map-based visualizations for geolocated time series collections, to allow for the timely retrieval of twin subsequences of interest that are also spatially closely located. TS-Index will pave the way towards seamless and interactive exploration of such data.

If you are interested in our work and would like to dive into more details, you can download a pre-print of the paper here.