TABLE OF CONTENTS We have presented efficient techniques to accurately compute the similarity between time-series with significant amount of noise. Our distance measure is based on the LCSS model and performs very well for noisy signals. Since the exact computation is inefficient, we presented approximate algorithms with provable performance bounds. Moreover, we presented an efficient index structure, which is based on hierarchical clustering, for similarity (nearest neighbor) queries. The distance that we use is not a metric and therefore the triangle inequality does not hold. However, we prove that a similar inequality holds (although a weaker one) that allows to prune parts of the datasets without any false dismissals.
Our experiments indicate that the approximation algorithm can be used to get an accurate and fast estimation of the distance between two time-series even under noisy conditions. Also, results from the index evaluation show that we can achieve good speed-ups for searching similar sequences comparing with the brute force linear scan.
We plan to investigate biased sampling to improve the running time of the approximation algorithms, especially when full rigid transformations (e.g. shifting, scaling and rotation) are necessary. Another approach to index time-series for similarity retrieval is to use embeddings and map the set of sequences to points in a low dimensional Euclidean space [15]. The challenge of course is to find an embedding that approximately preserves the original pairwise distances and gives good approximate results to similarity queries.
