# Dynamic Time Warping (DTW)

_This page describes the parameters for the Dynamic Time Warping (DTW) algorithm as part of AI libs._

Dynamic Time Warping (DTW) is a powerful algorithm used in temporal search to find patterns or sequences within time-series data that may vary in time or speed. By "warping" the time axis, DTW aligns similar parts of sequences, making it easier to compare them directly, even if they occur at different times or speeds.

## .ai.dtw.filterSearch

The `.ai.dtw.filterSearch` function returns the k best matches for q from ts under cutoff distance.

This function performs a DTW-based search to find the `k` best matches of a query time series within a larger dataset, but only returns results that fall under a specified cutoff distance. By applying this threshold, it filters out poor matches and ensures that only highly relevant sequences are returned.

### Parameters

| Name      | Type(s)                    | Description                                        |
|-----------|----------------------------|----------------------------------------------------|
| `ts`      | float[]                    | The timeseries `ts` to search on                   |
| `q`       | float[]                    | The pattern to search for                          |
| `k`       | short \| int \| long       | The number of best matches to return               |
| `window`  | short \| int \| long \| real \| float | The ratio of query size allowed in warping |
| `cutoff`  | short \| int \| long \| real \| float | The maximum distance (exclusive)        |
| `opts`    | dict                       | Advanced options(optional):   
- `ignoreErrors` (default `false`): if `true`, allows q longer than `ts` (returns empty).  
- `returnMatches` (default `false`): if `true`, returns a list of distances, indexes, and matched patterns.   
- `overlap` (default `0.0`): minimum distance between results expressed in ratio of of query size.|

### Returns

| Type            | Description                                     |
|-----------------|-------------------------------------------------|
| (float[];long[])| A list of distances and ids for nearest matches |

### Example
```q
q).ai:use`kx.ai
q)ts: neg[5.0] + 1000?10.0;
q)q:neg[5.0] + 10?10.0;
q).ai.dtw.filterSearch[ts;q;4;0.3;1.4;::]
1.336535 1.376232 1.39632
492      848      875 
```

The example creates a synthetic time series `ts` and a shorter query sequence q. It then searches for the 4 best matches of q in `ts`, but only returns those with a DTW distance below 1.4. The output shows three qualifying matches: the top row lists their DTW distances, and the second row lists the corresponding starting indices in `ts`.

## .ai.dtw.search

The `.ai.dtw.search` function returns k best matches for q from `ts`.

This function finds the `k` best matches of a query time series against a dataset using DTW similarity. Unlike `filterSearch`, it does not impose a distance cutoff, returning the top matches regardless of their alignment cost. It provides a flexible way to identify the closest temporal patterns in data, even if they vary in length or speed.

### Parameters

| Name      | Type(s)              | Description                             |
|-----------|----------------------|-----------------------------------------|
| `ts`      | float[]              | The timeseries to search on             |
| `q`       | float[]              | The pattern to search for               |
| `k`       | short \| int \| long | The number of best matches to return    |
| `window`  | short \| int \| long \| real \| float | The ratio of query size allowed in warping |
| `opts`    | dict              | Advanced options(optional):   
- `ignoreErrors` (default `false`): if `true`, allows q longer than `ts` (returns empty).  
- `returnMatches` (default `false`): if `true`, returns a list of distances, indexes, and matched patterns.   
- `overlap` (default `0.0`): minimum distance between results expressed in ratio of of query size.|

### Returns

| Type           | Description                                  |
|----------------|----------------------------------------------|
| (float[];long[])| A list of distances and ids for nearest matches |

### Example
```q
q).ai:use`kx.ai
q)ts: neg[5.0] + 1000?10.0;
q)q:neg[5.0] + 10?10.0;
q).ai.dtw.search[ts;q;4;0.3;::]
1.336535 1.376232 1.39632 1.41458
492      848      875     295
```

Here the same `ts` and `q` are used, but the function searches for the top 4 matches without enforcing a distance cutoff. As a result, it returns exactly four results, including one (index 295) that would have been excluded under the stricter cutoff. This demonstrates how search always returns `k` matches, regardless of distance.

## .ai.dtw.searchRange

The `.ai.dtw.searchRange` function returns the best matches for `q` from `ts` under cutoff distance.

This function searches for matches of a query time series within a dataset but only returns results that fall below a specified cutoff distance. Unlike `filterSearch`, it does not limit the output to exactly `k` results, but instead returns all qualifying matches.

### Parameters

| Name      | Type(s)           | Description                                                    |
|-----------|-------------------|----------------------------------------------------------------|
| `ts`      | float[]           | The timeseries to search on                                    |
| `q`       | float[]           | The pattern to search for                                      |
| `window`  | short \| int \| long \| real \| float | The ratio of query size allowed in warping |
| `cutoff`  | short \| int \| long \| real \| float | The maximum distance (exclusive)           |
| `opts`    | dict              | Advanced options (optional):   
- `ignoreErrors` (default `false`): if `true`, allows q longer than `ts` (returns empty).  
- `returnMatches` (default `false`): if `true`, returns a list of distances, indexes, and matched patterns.  
- `overlap` (default `0.0`): minimum distance between results expressed in ratio of of query size.|

### Returns

| Type           | Description                                  |
|----------------|----------------------------------------------|
| (float[];long[])| A list of distances and ids for nearest matches |

### Example
```q
q).ai:use`kx.ai
q)ts: neg[5.0] + 1000?10.0;
q)q:neg[5.0] + 10?10.0;
q).ai.dtw.searchRange[ts;q;0.3;1.4;::]
1.336535 1.376232 1.39632
492      848      875
```

This example performs a range search for `q` within `ts`, returning all subsequences whose DTW distance is below the cutoff 1.4. Unlike `filterSearch`, there is no `k` parameter, so the result count depends only on the threshold. The output shows the three matches that met the distance requirement, along with their starting indices.


## Next steps

- Read the [Dynamic time warping (DTW) with KDB-X](https://medium.com/kx-systems/tutorial-dynamic-time-warping-dtw-with-kdb-x-cb20fd241e41){target=_blank} tutorial on Medium.
