% This code is created by Abdullah Mueen, Krishnamurthy Viswanathan, Chetan Kumar Gupta and Eamonn Keogh.
% The overall time complexity of the code is O(n log n). The code is free to use for research purposes.
% The code may produce imaginary numbers due to numerical errors for long time series where batch processing on short segments can solve the problem.

function dist = findNN(x,y)

%x is the data, y is the query n = length(x); y = (y-mean(y))./std(y,1); %Normalize the query. If you do not want to normalize just comment this line. m = length(y); x(n+1:2*n) = 0; %Append zeros y = y(end:-1:1); %Reverse the query y(m+1:2*n) = 0; %Append zeros %The main trick of getting dot products in O(n log n) time. The algorithm is described in [a]. X = fft(x); %Change to Frequency domain Y = fft(y); %Change to Frequency domain Z = X.*Y; %Do the dot product z = ifft(Z); %Come back to Time domain %compute y stats -- O(n) sumy = sum(y); sumy2 = sum(y.^2); %compute x stats -- O(n) cum_sumx = cumsum(x); %Cumulative sums of x cum_sumx2 = cumsum(x.^2); %Cumulative sums of x^2 sumx2 = cum_sumx2(m+1:n)-cum_sumx2(1:n-m); %Sum of x^2 of every subsequences of length m sumx = cum_sumx(m+1:n)-cum_sumx(1:n-m); %Sum of x of every subsequences of length m meanx = sumx./m; %Mean of every subsequences of length m sigmax2 = (sumx2./m)-(meanx.^2); sigmax = sqrt(sigmax2); %Standard deviaiton of every subsequences of length m %computing the distances -- O(n) time. The formula is described in [b]. dist = (sumx2 - 2*sumx.*meanx + m*(meanx.^2))./sigmax2 - 2*(z(m+1:n) - sumy.*meanx)./sigmax + sumy2; dist = abs(sqrt(dist)); %If you want Pearson's correlation coefficients instead of Euclidean %Distance uncomment the next line. The formula is described in [c]. %CorrCoef = 1-abs(dist)./(2*m); end %[a] Abdullah Mueen, Hossein Hamooni, Trilce Estrada: Time Series Join on Subsequence Correlation. ICDM 2014: 450-459 %[b] Abdullah Mueen, Eamonn J. Keogh, Neal Young: Logical-shapelets: an expressive primitive for time series classification. KDD 2011: 1154-1162 %[c] Abdullah Mueen, Suman Nath, Jie Liu: Fast approximate correlation for massive time-series data. SIGMOD Conference 2010: 171-182