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).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).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).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 tutorial on Medium.