src/UCRDTW_kNN_serial.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 significant 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 significant 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 significant 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 .
double lb_kim_hierarchy(double * t, double * q, int j, int len, double mean, double std, double bsf = INF)
{
    double d, lb;
    double x0 = (t[j] - mean) / std;
    double y0 = (t[(len-1+j)] - mean) / std;
    lb = dist(x0,q[0]) + dist(y0,q[len-1]);
    if (lb >= bsf)   return lb;
    double x1 = (t[(j+1)] - mean) / std;
    d = min(dist(x1,q[0]), dist(x0,q[1]));
    d = min(d, dist(x1,q[1]));
    lb += d;
    if (lb >= bsf)   return lb;
    double y1 = (t[(len-2+j)] - mean) / std;
    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;
    double x2 = (t[(j+2)] - mean) / std;
    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;
    double y2 = (t[(len-3+j)] - mean) / std;
    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;
}
double lb_kim_hierarchy ( double * t , double * q , int j , int len , double mean , double std , double bsf = INF ) { double d , lb ; double x0 = ( t [ j ] - mean ) / std ; double y0 = ( t [ ( len - 1 + j ) ] - mean ) / std ; lb = dist ( x0 , q [ 0 ] ) + dist ( y0 , q [ len - 1 ] ) ; if ( lb >= bsf ) return lb ; double x1 = ( t [ ( j + 1 ) ] - mean ) / std ; d = min ( dist ( x1 , q [ 0 ] ) , dist ( x0 , q [ 1 ] ) ) ; d = min ( d , dist ( x1 , q [ 1 ] ) ) ; lb += d ; if ( lb >= bsf ) return lb ; double y1 = ( t [ ( len - 2 + j ) ] - mean ) / std ; 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 ; double x2 = ( t [ ( j + 2 ) ] - mean ) / std ; 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 ; double y2 = ( t [ ( len - 3 + j ) ] - mean ) / std ; 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