Faster Sequential Search with a Two-Pass Dynamic-Time-Warping Lower Bound

Details Faster Sequential Search with a Two-Pass Dynamic-Time-Warping Lower Bound Faster Sequential Search with a Two-Pass Dynamic-Time-Warping Lower Bound

2008-07-10

arxiv.org/abs/0807.1734v5

Computer Science

Databases

Scientific paper

The Dynamic Time Warping (DTW) is a popular similarity measure between time series. The DTW fails to satisfy the triangle inequality and its computation requires quadratic time. Hence, to find closest neighbors quickly, we use bounding techniques. We can avoid most DTW computations with an inexpensive lower bound (LB_Keogh). We compare LB_Keogh with a tighter lower bound (LB_Improved). We find that LB_Improved-based search is faster for sequential search. As an example, our approach is 3 times faster over random-walk and shape time series. We also review some of the mathematical properties of the DTW. We derive a tight triangle inequality for the DTW. We show that the DTW becomes the l_1 distance when time series are separated by a constant.

Affiliated with

Also associated with

No associations

Rating

Faster Sequential Search with a Two-Pass Dynamic-Time-Warping Lower Bound does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Faster Sequential Search with a Two-Pass Dynamic-Time-Warping Lower Bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Sequential Search with a Two-Pass Dynamic-Time-Warping Lower Bound will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-574624