Scalable kNN Search on Vertically Stored Time Series. Panagiotis Karras. Talk

Want a method that scales knn on time series efficiently both in terms of number of time series as well as length of the time series

Methods are based on some form of dimension reduction (PCA is common)

Because dimensions are thrown out, introduces some innacuracy. Want to establish that the distance you have here is a lower bound on the actual distance

I guess this projects the time series into feature vectors of same size

Actually, all time series must be the same length

VA-file is an algorithm that does not do indexing, which was unique at the time it was published, won a 10-year best paper award

But in general there is some compact representation that indexes the large data, and you have to go back and forth between the compact and full data

The approach here introduces a step when going from the index to the full data

The idea is to have a sequences of indices – from very compact (and erroneous) to progressively larger and more complete

This can be improved further by having all the indices together to comprise the full data set

This method, however, requires both an upper and lower bound on distances (both bounds are needed to do more pruning)

The derivation of the bounds are based on a Haar Wavelet Transform

Constructs a tree, where each node has some piece of information that is used to assemble the final information at the leaf (for example, numbers in nodes that you add together going from root to leaf

The method used here has both an upper and lower bound, as well as much tighter bounds than were previously used

<Not going into details of how the bounds are actually computed>

As you would expect, the empirical results are good

Multiple type of transforms can be used (cosine, fourier)

Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
To find out more, including how to control cookies, see here:
Cookie Policy