A segmented approach for efficient similarity search supporting time warping for both with and without warping envelop constraint

Speaker: Sindy SHOU

Abstract

Efficient similarity search in sequence databases has attracted a lot of research interest, because it has a lot of different kinds of applications. A typical application could be: an investor may wish to know the stocks which behave similarly to a certain query stock. Nowadays, many researches are focusing on the efficient similarity search supporting time warping instead of using Euclidean distance metric because dynamic time warping (DTW) allows elastic shifting of the X-axis in order to detect similar shapes with different phases, which turns out to be more robust than Euclidean distance metric. However, recent works have only proposed efficient algorithms to solve the problem in the case either with or without envelop constraint. In this paper, we propose a segmented approach to solve the similarity search supporting time warping for both with or without envelop constraint. Several improvements have also been proposed to improve the lower bounding functions of DTW distance and the experimental results show the superior of our proposed lower bounding functions.

Referred Papers