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


  1. 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
  2. Methods are based on some form of dimension reduction (PCA is common) 
    1. 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
  3. I guess this projects the time series into feature vectors of same size
    1. Actually, all time series must be the same length
  4. 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
  5. 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
  6. The approach here introduces a step when going from the index to the full data
  7. The idea is to have a sequences of indices – from very compact (and erroneous) to progressively larger and more complete
  8. This can be improved further by having all the indices together to comprise the full data set
  9. This method, however, requires both an upper and lower bound on distances (both bounds are needed to do more pruning)
  10. The derivation of the bounds are based on a Haar Wavelet Transform
    1. 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
  11. The method used here has both an upper and lower bound, as well as much tighter bounds than were previously used
  12. <Not going into details of how the bounds are actually computed>
  13. As you would expect, the empirical results are good
  14. Multiple type of transforms can be used (cosine, fourier)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: