- 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)

Advertisements
(function(g,$){if("undefined"!=typeof g.__ATA){
g.__ATA.initAd({collapseEmpty:'after', sectionId:26942, width:300, height:250});
g.__ATA.initAd({collapseEmpty:'after', sectionId:114160, width:300, height:250});
}})(window,jQuery);
var o = document.getElementById('crt-612229454');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-612229454",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-612229454'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}
var o = document.getElementById('crt-1566901081');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-1566901081",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-1566901081'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}