src/UCRDTW_memory_parallel.cpp
/// Calculate quick lower bound
/// Usually, LB_Kim take time O(m) for finding top,bottom,fist and last.
/// However, because of z-normalization the top and bottom cannot give siginifant benefits.
/// And using the first and last points can be computed in constant time.
/// The prunning power of LB_Kim is non-trivial, especially when the query is not long, say in length 128.
Calculate quick lower bound
Usually, LB_Kim take time O(m) for finding top,bottom,fist and last.
However, because of z-normalization the top and bottom cannot give siginifant benefits.
And using the first and last points can be computed in constant time.
The prunning power of LB_Kim is non-trivial, especially when the query is not long, say in length 128.
Calculate quick lower bound Usually LB_Kim take time O ( m ) for finding top bottom fist and last . However because of z - normalization the top and bottom cannot give siginifant benefits . And using the first and last points can be computed in constant time . The prunning power of LB_Kim is non - trivial especially when the query is not long say in length 128 .
float lb_kim_hierarchy(float *t, float *q, int j, int len, float mean, float std, _Bool bNormalized, float bsf = FLT_MAX)
{
    float d, lb;
    float x0;
    float y0;
    if (bNormalized)
    {
        x0 = (t[j] - mean) / std;
        y0 = (t[(len - 1 + j)] - mean) / std;
    }
    else
    {
        x0 = t[j];
        y0 = t[(len - 1 + j)];
    }
    lb = dist(x0, q[0]) + dist(y0, q[len - 1]);
    if (lb >= bsf)
        return lb;
    float x1;
    if (bNormalized)
        x1 = (t[(j + 1)] - mean) / std;
    else
        x1 = t[(j + 1)];
    d = min(dist(x1, q[0]), dist(x0, q[1]));
    d = min(d, dist(x1, q[1]));
    lb += d;
    if (lb >= bsf)
        return lb;
    float y1;
    if (bNormalized)
        y1 = (t[(len - 2 + j)] - mean) / std;
    else
        y1 = t[(len - 2 + j)];
    d = min(dist(y1, q[len - 1]), dist(y0, q[len - 2]));
    d = min(d, dist(y1, q[len - 2]));
    lb += d;
    if (lb >= bsf)
        return lb;
    float x2;
    if (bNormalized)
        x2 = (t[(j + 2)] - mean) / std;
    else
        x2 = t[(j + 2)];
    d = min(dist(x0, q[2]), dist(x1, q[2]));
    d = min(d, dist(x2, q[2]));
    d = min(d, dist(x2, q[1]));
    d = min(d, dist(x2, q[0]));
    lb += d;
    if (lb >= bsf)
        return lb;
    float y2;
    if (bNormalized)
        y2 = (t[(len - 3 + j)] - mean) / std;
    else
        y2 = t[(len - 3 + j)];
    d = min(dist(y0, q[len - 3]), dist(y1, q[len - 3]));
    d = min(d, dist(y2, q[len - 3]));
    d = min(d, dist(y2, q[len - 2]));
    d = min(d, dist(y2, q[len - 1]));
    lb += d;
    return lb;
}
float lb_kim_hierarchy ( float * t , float * q , int j , int len , float mean , float std , _Bool bNormalized , float bsf = FLT_MAX ) { float d , lb ; float x0 ; float y0 ; if ( bNormalized ) { x0 = ( t [ j ] - mean ) / std ; y0 = ( t [ ( len - 1 + j ) ] - mean ) / std ; } else { x0 = t [ j ] ; y0 = t [ ( len - 1 + j ) ] ; } lb = dist ( x0 , q [ 0 ] ) + dist ( y0 , q [ len - 1 ] ) ; if ( lb >= bsf ) return lb ; float x1 ; if ( bNormalized ) x1 = ( t [ ( j + 1 ) ] - mean ) / std ; else x1 = t [ ( j + 1 ) ] ; d = min ( dist ( x1 , q [ 0 ] ) , dist ( x0 , q [ 1 ] ) ) ; d = min ( d , dist ( x1 , q [ 1 ] ) ) ; lb += d ; if ( lb >= bsf ) return lb ; float y1 ; if ( bNormalized ) y1 = ( t [ ( len - 2 + j ) ] - mean ) / std ; else y1 = t [ ( len - 2 + j ) ] ; d = min ( dist ( y1 , q [ len - 1 ] ) , dist ( y0 , q [ len - 2 ] ) ) ; d = min ( d , dist ( y1 , q [ len - 2 ] ) ) ; lb += d ; if ( lb >= bsf ) return lb ; float x2 ; if ( bNormalized ) x2 = ( t [ ( j + 2 ) ] - mean ) / std ; else x2 = t [ ( j + 2 ) ] ; d = min ( dist ( x0 , q [ 2 ] ) , dist ( x1 , q [ 2 ] ) ) ; d = min ( d , dist ( x2 , q [ 2 ] ) ) ; d = min ( d , dist ( x2 , q [ 1 ] ) ) ; d = min ( d , dist ( x2 , q [ 0 ] ) ) ; lb += d ; if ( lb >= bsf ) return lb ; float y2 ; if ( bNormalized ) y2 = ( t [ ( len - 3 + j ) ] - mean ) / std ; else y2 = t [ ( len - 3 + j ) ] ; d = min ( dist ( y0 , q [ len - 3 ] ) , dist ( y1 , q [ len - 3 ] ) ) ; d = min ( d , dist ( y2 , q [ len - 3 ] ) ) ; d = min ( d , dist ( y2 , q [ len - 2 ] ) ) ; d = min ( d , dist ( y2 , q [ len - 1 ] ) ) ; lb += d ; return lb ; }
Calculate quick lower bound
Usually, LB_Kim take time O(m) for finding top,bottom,fist and last.
Calculate quick lower bound Usually LB_Kim take time O ( m ) for finding top bottom fist and last .
/// 1 point at front and back /// 2 points at front /// 2 points at back /// 3 points at front /// 3 points at back