src/UCRDTW_memory_parallel.cpp
float dtw(float *A, float *B, float *cb, int m, int r, int *pointChecked, float bsf = FLT_MAX)
{

    float *cost;
    float *cost_prev;
    float *cost_tmp;
    int i, j, k;
    float x, y, z, min_cost;

    /// Instead of using matrix of size O(m^2) or O(mr), we will reuse two array of size O(r).
    cost = (float *)malloc(sizeof(float) * (2 * r + 1));
    for (k = 0; k < 2 * r + 1; k++)
        cost[k] = FLT_MAX;

    cost_prev = (float *)malloc(sizeof(float) * (2 * r + 1));
    for (k = 0; k < 2 * r + 1; k++)
        cost_prev[k] = FLT_MAX;

    for (i = 0; i < m; i++)
    {
        k = max(0, r - i);
        min_cost = FLT_MAX;

        for (j = max(0, i - r); j <= min(m - 1, i + r); j++, k++)
        {
            /// Initialize all row and column
            if ((i == 0) && (j == 0))
            {
                cost[k] = dist(A[0], B[0]);
                min_cost = cost[k];
                continue;
            }

            if ((j - 1 < 0) || (k - 1 < 0))
                y = FLT_MAX;
            else
                y = cost[k - 1];
            if ((i - 1 < 0) || (k + 1 > 2 * r))
                x = FLT_MAX;
            else
                x = cost_prev[k + 1];
            if ((i - 1 < 0) || (j - 1 < 0))
                z = FLT_MAX;
            else
                z = cost_prev[k];

            /// Classic DTW calculation
            cost[k] = min(min(x, y), z) + dist(A[i], B[j]);

            /// Find minimum cost in row for early abandoning (possibly to use column instead of row).
            if (cost[k] < min_cost)
            {
                min_cost = cost[k];
            }
        }

        /// We can abandon early if the current cummulative distace with lower bound together are larger than bsf
        if (i + r < m - 1 && min_cost + cb[i + r + 1] >= bsf)
        {
            free(cost);
            free(cost_prev);
            return min_cost + cb[i + r + 1];
        }

        /// Move current array to previous array.
        cost_tmp = cost;
        cost = cost_prev;
        cost_prev = cost_tmp;
        (*pointChecked)++;
    }
    k--;

    /// the DTW distance is in the last cell in the matrix of size O(m^2) or at the middle of our array.
    float final_dtw = cost_prev[k];
    free(cost);
    free(cost_prev);
    return final_dtw;
}
/// Calculate Dynamic Time Wrapping distance
/// A,B: data and query, respectively
/// cb : cummulative bound used for early abandoning
/// r  : size of Sakoe-Chiba warpping band
Calculate Dynamic Time Wrapping distance
A,B: data and query, respectively
cb : cummulative bound used for early abandoning
r  : size of Sakoe-Chiba warpping band
Calculate Dynamic Time Wrapping distance A B : data and query respectively cb : cummulative bound used for early abandoning r : size of Sakoe - Chiba warpping band
float dtw(float *A, float *B, float *cb, int m, int r, int *pointChecked, float bsf = FLT_MAX)
{
    float *cost;
    float *cost_prev;
    float *cost_tmp;
    int i, j, k;
    float x, y, z, min_cost;
    cost = (float *)malloc(sizeof(float) * (2 * r + 1));
    for (k = 0; k < 2 * r + 1; k++)
        cost[k] = FLT_MAX;
    cost_prev = (float *)malloc(sizeof(float) * (2 * r + 1));
    for (k = 0; k < 2 * r + 1; k++)
        cost_prev[k] = FLT_MAX;
    for (i = 0; i < m; i++)
    {
        k = max(0, r - i);
        min_cost = FLT_MAX;
        for (j = max(0, i - r); j <= min(m - 1, i + r); j++, k++)
        {
            if ((i == 0) && (j == 0))
            {
                cost[k] = dist(A[0], B[0]);
                min_cost = cost[k];
                continue;
            }
            if ((j - 1 < 0) || (k - 1 < 0))
                y = FLT_MAX;
            else
                y = cost[k - 1];
            if ((i - 1 < 0) || (k + 1 > 2 * r))
                x = FLT_MAX;
            else
                x = cost_prev[k + 1];
            if ((i - 1 < 0) || (j - 1 < 0))
                z = FLT_MAX;
            else
                z = cost_prev[k];
            cost[k] = min(min(x, y), z) + dist(A[i], B[j]);
            if (cost[k] < min_cost)
            {
                min_cost = cost[k];
            }
        }
        if (i + r < m - 1 && min_cost + cb[i + r + 1] >= bsf)
        {
            free(cost);
            free(cost_prev);
            return min_cost + cb[i + r + 1];
        }
        cost_tmp = cost;
        cost = cost_prev;
        cost_prev = cost_tmp;
        (*pointChecked)++;
    }
    k--;
    float final_dtw = cost_prev[k];
    free(cost);
    free(cost_prev);
    return final_dtw;
}
float dtw ( float * A , float * B , float * cb , int m , int r , int * pointChecked , float bsf = FLT_MAX ) { float * cost ; float * cost_prev ; float * cost_tmp ; int i , j , k ; float x , y , z , min_cost ; cost = ( float * ) malloc ( sizeof ( float ) * ( 2 * r + 1 ) ) ; for ( k = 0 ; k < 2 * r + 1 ; k ++ ) cost [ k ] = FLT_MAX ; cost_prev = ( float * ) malloc ( sizeof ( float ) * ( 2 * r + 1 ) ) ; for ( k = 0 ; k < 2 * r + 1 ; k ++ ) cost_prev [ k ] = FLT_MAX ; for ( i = 0 ; i < m ; i ++ ) { k = max ( 0 , r - i ) ; min_cost = FLT_MAX ; for ( j = max ( 0 , i - r ) ; j <= min ( m - 1 , i + r ) ; j ++ , k ++ ) { if ( ( i == 0 ) && ( j == 0 ) ) { cost [ k ] = dist ( A [ 0 ] , B [ 0 ] ) ; min_cost = cost [ k ] ; continue ; } if ( ( j - 1 < 0 ) || ( k - 1 < 0 ) ) y = FLT_MAX ; else y = cost [ k - 1 ] ; if ( ( i - 1 < 0 ) || ( k + 1 > 2 * r ) ) x = FLT_MAX ; else x = cost_prev [ k + 1 ] ; if ( ( i - 1 < 0 ) || ( j - 1 < 0 ) ) z = FLT_MAX ; else z = cost_prev [ k ] ; cost [ k ] = min ( min ( x , y ) , z ) + dist ( A [ i ] , B [ j ] ) ; if ( cost [ k ] < min_cost ) { min_cost = cost [ k ] ; } } if ( i + r < m - 1 && min_cost + cb [ i + r + 1 ] >= bsf ) { free ( cost ) ; free ( cost_prev ) ; return min_cost + cb [ i + r + 1 ] ; } cost_tmp = cost ; cost = cost_prev ; cost_prev = cost_tmp ; ( * pointChecked ) ++ ; } k -- ; float final_dtw = cost_prev [ k ] ; free ( cost ) ; free ( cost_prev ) ; return final_dtw ; }
Calculate Dynamic Time Wrapping distance
A,B: data and query, respectively
cb : cummulative bound used for early abandoning
r  : size of Sakoe-Chiba warpping band
Calculate Dynamic Time Wrapping distance A B : data and query respectively cb : cummulative bound used for early abandoning r : size of Sakoe - Chiba warpping band
/// Instead of using matrix of size O(m^2) or O(mr), we will reuse two array of size O(r). /// Initialize all row and column /// Classic DTW calculation /// Find minimum cost in row for early abandoning (possibly to use column instead of row). /// We can abandon early if the current cummulative distace with lower bound together are larger than bsf /// Move current array to previous array. /// the DTW distance is in the last cell in the matrix of size O(m^2) or at the middle of our array.