Time Series Embeddings for Similarity Search

Two demand curves with the same shape one week apart are similar to a human and far apart in Euclidean distance. Dynamic time warping fixes that and cannot be indexed; learned embeddings can be indexed and lose some of what warping caught. The choice between them is an indexing property, not a taste.

Why Euclidean distance fails on shape

Point-to-point distance compares position i to position i. Any shift along the time axis — a promotion that ran a week later, a sensor that started recording a second early — is charged as if the values were different, when what changed was the alignment.

Take two sequences that are the same shape offset by one step:

a = [0, 1, 2, 3, 2, 1, 0]
b = [0, 0, 1, 2, 3, 2, 1]

Pointwise absolute differences are 0, 1, 1, 1, 1, 1, 1, summing to 6. In squared terms the distance is √6 = 2.449. Nothing in those numbers says “these are the same event, one step apart” — the metric has no way to express that, because it has no freedom in the alignment.

DTW on a labelled pair

Dynamic time warping, introduced for speech recognition by Hiroaki Sakoe and Seibi Chiba in 1978, finds the alignment between two sequences that minimises total cost, subject to three constraints: the alignment starts at the first element of each and ends at the last, it never goes backwards, and it never skips an element. Within those rules a single element of one sequence may match several of the other, which is the warping.

Align the two sequences above by hand under those rules:

b[0]=0  ↔  a[0]=0     cost 0
b[1]=0  ↔  a[0]=0     cost 0     ← a[0] reused: this is the warp
b[2]=1  ↔  a[1]=1     cost 0
b[3]=2  ↔  a[2]=2     cost 0
b[4]=3  ↔  a[3]=3     cost 0
b[5]=2  ↔  a[4]=2     cost 0
b[6]=1  ↔  a[5]=1     cost 0
b[6]=1  ↔  a[6]=0     cost 1     ← forced: the path must end at both last elements

DTW  = 1        pointwise (|·|) = 6

One instead of six, and the residual 1 is not noise — it comes from the boundary constraint. The path must terminate at the last element of both sequences, so a’s trailing 0 has nowhere aligned to go but b’s trailing 1. That endpoint rigidity is a real property of DTW and it is why a series with a ragged tail can score worse than its shape deserves. Open-end and open-begin DTW variants exist precisely to relax it.

Two practical notes before this goes anywhere near a dataset. Compute cost is O(n·m) for two sequences of length n and m, because the algorithm fills a full cost matrix. The standard fix is the Sakoe-Chiba band, which forbids the path from straying more than w cells from the diagonal, giving O(n·w) and, as a side effect, forbidding absurd alignments where one point absorbs half the other series. And z-normalise before comparing shapes: on unnormalised series DTW ranks mostly by amplitude, so your nearest neighbours are whatever sells the most.

Why DTW cannot go in a vector index

This is the property that decides the architecture, and it is usually left out. DTW is not a metric. It violates the triangle inequality: there exist sequences where DTW(a,c) > DTW(a,b) + DTW(b,c).

Approximate nearest neighbour indexes rely on the triangle inequality to prune. It is what lets a graph index conclude that a whole region cannot contain a closer neighbour without visiting it — the reasoning behind HNSW and every other structure of that kind. Take the inequality away and the pruning is unsound, so a DTW search over N stored series is a linear scan: N full dynamic-programming computations per query.

At ten thousand series of length 500 with a band of 50, that is 10,000 × 500 × 50 = 250 million cell evaluations per query. Tractable once, not tractable as an interactive lookup, and not tractable at all at a million series. The established mitigation is the LB_Keogh lower bound, published by Eamonn Keogh, which computes a cheap lower bound on the DTW distance and skips the full computation whenever the bound already exceeds the best distance found so far. It makes a linear scan much faster. It does not make it sublinear.

What a learned embedding replaces it with

An embedding maps a variable-length series to a fixed-length vector, after which cosine or Euclidean distance applies, which means the whole approximate-nearest-neighbour toolchain applies. You trade exact shape alignment for sublinear search. Three families, in increasing order of how much they need from you:

• Hand-designed feature sets. The catch22 feature set of Carl Lubba and colleagues reduces a series to 22 canonical time-series characteristics selected from a much larger library for performance and low redundancy. Fast, deterministic, and each dimension has a name you can explain.
• Random convolutional features. ROCKET, by Angus Dempster, François Petitjean and Geoffrey Webb, convolves the series with a large number of random kernels — the reference implementation defaults to 10,000 — and takes two features from each: the maximum and the proportion of positive values. The kernels are never trained. The paper reports state-of-the-art classification accuracy at a fraction of the computational expense of the methods it was compared against, which makes it a very strong baseline before you consider training anything.
• Learned representations. Contrastive methods such as TS2Vec train an encoder so that augmented views of the same window land close together. These can encode domain structure the other two cannot, at the cost of a training run, a labelled or at least curated corpus, and the drift problem — an encoder trained last year embeds this year’s series slightly differently, and your index does not know.

Whichever you pick, the embedding must be invariant to what you want to ignore and sensitive to what you want to find. If you z-normalise before encoding, two series with the same shape at different volumes become neighbours — which is right for “find me a similar demand pattern” and wrong for “find me another SKU of this size”. Nothing downstream can recover a distinction you removed at encoding time.

Which to use

Use DTW when the corpus is small enough to scan, the alignment genuinely matters, and you need the distance to be explainable — a warping path is a picture you can show someone. Use embeddings when the corpus is large, the query has to be fast, or the notion of similarity is more abstract than shape.

The arrangement that gets the most out of both is a two-stage retrieval: embed everything, pull the top few hundred candidates from the vector index in milliseconds, then re-rank those candidates with banded DTW. The index supplies recall, the exact distance supplies precision, and the linear scan runs over hundreds of series rather than millions. It is the same shape as reranking a first-pass retrieval anywhere else.

The most common use for this in forecasting is finding analogues for a series with no history — matching a new SKU to established ones and borrowing their curve. That is cold-start forecasting, and the quality of the match is the whole forecast, so it is worth the re-ranking stage.