Similarity search between time series in Matlab. Possible ? I cant find R-tree implementation in matlab

Question

I would like to implement similarity search in matlab. I wanna to know is it possible ?

My plan is to do use 2 popular similarity measurement which are Euclidean Distance and Dynamic Time Warping. Both of these will be applied on time series dataset. My question at this point is how can I evaluate both of these two measurement performance and accuracy ? I seen some literature saying i should use K-NN algorithm.

Then, I plan to apply dimensionality reduction on the time series dataset. After reducued the dimensionality of the dataset. I will need to index the dataset using R-tree or any indexing techniques available.

However my problem is that to do this, I need R-tree matlab code which I hardly able to find any in the internet ...

I do realised that most of the implementation for similarity search are in C++, C and Java ... But im not familiar with those. Im hoping I could implement these in Matlab ... Any Guru could help me with this ?

Also what kind of evaluation can I make to evaluate the performance for each algorithm.

Thanks

Answer 1

Recently (R2010a I believe), MATLAB added new functions for k-Nearest Neighbor (kNN) searching using KD-tree (a spatial indexing method similar to R-tree) to the Statistics Toolbox. Example:

load fisheriris                            % Iris dataset
Q = [6 3 4 1 ; 5 4 3 2];                   % query points

% build kd-tree
knnObj = createns(meas, 'NSMethod','kdtree', 'Distance','euclidean');

% find k=5 Nearest Neighbors to Q
[idx Dist] = knnsearch(knnObj, Q, 'K',5);

Refer to this page for nice description.

Also if you have the Image Processing Toolbox, it contains (for a long time now) an implementation of the kd-tree and kNN searching. They are private functions though:

[matlabroot '\images\images\private\kdtree.m']
[matlabroot '\images\images\private\nnsearch.m']

To compare your two approaches (Dynamic Time Warping and Euclidean distance), you can design a classic problem of classification; given a set of labeled training/testing time series, the task is to predict the label of each test sequenceby finding the most similar ones using kNN then predict the majority class. To evaluate performance, use any of the standard measures of classification like accuracy/error, etc..

Answer 2

It turns out that it is MUCH faster, for both ED and DTW, to do a sequential scan, using the UCR suite.

See this video https://www.youtube.com/watch?v=d_qLzMMuVQg

or this

https://www.youtube.com/watch?v=c7xz9pVr05Q

the code is free http://www.cs.ucr.edu/~eamonn/UCRsuite.html