src/UCRDTW_memory_parallel.cpp
/// Finding the envelop of min and max value for LB_Keogh
/// Implementation idea is intoruduced by Danial Lemire in his paper
/// "Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound", Pattern Recognition 42(9), 2009.
Finding the envelop of min and max value for LB_Keogh
Implementation idea is intoruduced by Danial Lemire in his paper
"Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound", Pattern Recognition 42(9), 2009.
Finding the envelop of min and max value for LB_Keogh Implementation idea is intoruduced by Danial Lemire in his paper " Faster Retrieval with a Two - Pass Dynamic - Time - Warping Lower Bound " Pattern Recognition 42 ( 9 ) 2009 .
void lower_upper_lemire(float *t, int len, int r, float *l, float *u)
{
    struct deque du, dl;
    init(&du, 2 * r + 2);
    init(&dl, 2 * r + 2);
    push_back(&du, 0);
    push_back(&dl, 0);
    for (int i = 1; i < len; i++)
    {
        if (i > r)
        {
            u[i - r - 1] = t[front(&du)];
            l[i - r - 1] = t[front(&dl)];
        }
        if (t[i] > t[i - 1])
        {
            pop_back(&du);
            while (!empty(&du) && t[i] > t[back(&du)])
                pop_back(&du);
        }
        else
        {
            pop_back(&dl);
            while (!empty(&dl) && t[i] < t[back(&dl)])
                pop_back(&dl);
        }
        push_back(&du, i);
        push_back(&dl, i);
        if (i == 2 * r + 1 + front(&du))
            pop_front(&du);
        else if (i == 2 * r + 1 + front(&dl))
            pop_front(&dl);
    }
    for (int i = len; i < len + r + 1; i++)
    {
        u[i - r - 1] = t[front(&du)];
        l[i - r - 1] = t[front(&dl)];
        if (i - front(&du) >= 2 * r + 1)
            pop_front(&du);
        if (i - front(&dl) >= 2 * r + 1)
            pop_front(&dl);
    }
    destroy(&du);
    destroy(&dl);
}
void lower_upper_lemire ( float * t , int len , int r , float * l , float * u ) { struct deque du , dl ; init ( & du , 2 * r + 2 ) ; init ( & dl , 2 * r + 2 ) ; push_back ( & du , 0 ) ; push_back ( & dl , 0 ) ; for ( int i = 1 ; i < len ; i ++ ) { if ( i > r ) { u [ i - r - 1 ] = t [ front ( & du ) ] ; l [ i - r - 1 ] = t [ front ( & dl ) ] ; } if ( t [ i ] > t [ i - 1 ] ) { pop_back ( & du ) ; while ( ! empty ( & du ) && t [ i ] > t [ back ( & du ) ] ) pop_back ( & du ) ; } else { pop_back ( & dl ) ; while ( ! empty ( & dl ) && t [ i ] < t [ back ( & dl ) ] ) pop_back ( & dl ) ; } push_back ( & du , i ) ; push_back ( & dl , i ) ; if ( i == 2 * r + 1 + front ( & du ) ) pop_front ( & du ) ; else if ( i == 2 * r + 1 + front ( & dl ) ) pop_front ( & dl ) ; } for ( int i = len ; i < len + r + 1 ; i ++ ) { u [ i - r - 1 ] = t [ front ( & du ) ] ; l [ i - r - 1 ] = t [ front ( & dl ) ] ; if ( i - front ( & du ) >= 2 * r + 1 ) pop_front ( & du ) ; if ( i - front ( & dl ) >= 2 * r + 1 ) pop_front ( & dl ) ; } destroy ( & du ) ; destroy ( & dl ) ; }
Finding the envelop of min and max value for LB_Keogh
Implementation idea is intoruduced by Danial Lemire in his paper
"Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound", Pattern Recognition 42(9), 2009.
Finding the envelop of min and max value for LB_Keogh Implementation idea is intoruduced by Danial Lemire in his paper " Faster Retrieval with a Two - Pass Dynamic - Time - Warping Lower Bound " Pattern Recognition 42 ( 9 ) 2009 .