Error-bounded approximate time series join using compact dictionary representation of time series

Patent metadata

Field	Value
Publication number	US-12423300-B2
Application number	US-202218567717-A
Country	US
Kind code	B2
Filing date	Jun 1, 2022
Priority date	Jun 7, 2021
Publication date	Sep 23, 2025
Grant date	Sep 23, 2025

Abstract

A method is disclosed. The method comprises determining a time series, a subsequence length. The length of the time series may then be determined, and an initial matrix profile may then be computed. The method may then form a processed matrix profile for a first subsequence of the subsequence length by applying the first subsequence to the initial matrix profile. A second subsequence may then be determined from the processed matrix profile. The method may then include comparing the second subsequence to other subsequences in a dictionary and adding it to the dictionary. The subsequences in the dictionary may be used to generate a plurality of subsequence matrix profiles. The method may then include forming an approximate matrix profile using the plurality of subsequence matrix profiles and then determining one or more anomalies in the time series or another time series using the approximate matrix profile.

First claim

What is claimed is:

1. A method comprising:
a) determining, by a server computer, a time series corresponding to time-dependent events;
b) determining, by the server computer, a subsequence length;
c) determining a length of the time series;
d) computing, by the server computer, an initial matrix profile using the time series;
e) forming, by the server computer, a processed matrix profile for a first subsequence of the subsequence length by applying the first subsequence to the initial matrix profile;
f) determining, by the server computer, a second subsequence from the processed matrix profile;
g) adding, by the server computer, the determined second subsequence to a dictionary comprising a subset of subsequences in the time series;
h) generating, by the server computer, a plurality of subsequence matrix profiles by applying the subset of subsequences in the dictionary to the time series or another time series;
i) forming, by the server computer, an approximate matrix profile by taking element-wise minimums of the plurality of subsequence matrix profiles; and
j) determining one or more anomalies in the time series using the approximate matrix profile.

2. The method of claim 1 wherein the initial matrix profile is generated by:
a-1) determining a subsequence of the time series;
b-1) applying the subsequence to the time series to form a distance profile;
c-1) repeating a)-1 and b)-1 for each subsequence in the time series; and
d-1) forming the initial matrix profile using the distance profiles.

3. The method of claim 1 , wherein steps e)-h) are repeated until all subsequences in the time series are processed.

4. The method of claim 1 , wherein the determined second subsequence is added in the dictionary if the second subsequence or a subsequence substantially similar to the second subsequence is not stored in the dictionary.

5. The method of claim 1 , wherein after f) determining the second subsequence from the processed matrix profile, the method further comprises:
comparing, by the server computer, the second subsequence to other subsequences in the dictionary.

6. The method of claim 5 , wherein as a result of comparing the second subsequence to the other subsequences in the dictionary results in combining the second subsequence with an overlapping subsequence in the dictionary.

7. The method of claim 1 , wherein forming the approximate matrix profile using the plurality of subsequence matrix profiles comprises performing an element-wise minimum operation on the plurality of subsequence matrix profiles.

8. The method of claim 1 , wherein j) determining one or more anomalies in the time series using the approximate matrix profile comprises determining a maximum value of the approximate matrix profile.

9. The method of claim 1 , wherein the subsequence length corresponds to a length of a subsequence in the time series.

10. The method of claim 1 , wherein the method further comprises determining a contextual window factor, wherein the contextual window factor is a value that adjusts the subsequence length.

11. The method of claim 1 , wherein the plurality of subsequence matrix profiles are generated until a terminal condition is met.

12. The method of claim 11 , wherein the terminal condition is based on a max error.

13. The method of claim 1 , wherein the subsequence length is determined based upon a shape of the time series.

14. A server computer comprising:
a processor; and
a non-transitory computer readable medium comprising instructions executable by the processor to perform operations including:
a) determining a time series corresponding to time-dependent events;
b) determining a subsequence length;
c) determining a length of the time series;
d) computing an initial matrix profile using the time series;
e) forming a processed matrix profile for a first subsequence of the subsequence length by applying the first subsequence to the initial matrix profile;
f) determining a second subsequence from the processed matrix profile;
g) adding the determined second subsequence to a dictionary comprising a subset of subsequences in the time series;
h) generating a plurality of subsequence matrix profiles by applying the subset of subsequences in the dictionary to the time series or another time series;
i) forming an approximate matrix profile by taking element-wise minimums of the plurality of subsequence matrix profiles; and
j) determining one or more anomalies in the time series using the approximate matrix profile.

15. The server computer of claim 14 , wherein the initial matrix profile is generated by:
a-1) determining a subsequence of the time series;
b-1) applying the subsequence to the time series to form a distance profile;
c-1) repeating a)-1 and b)-1 for each subsequence in the time series; and
d-1) forming the initial matrix profile using the distance profiles.

16. The server computer of claim 14 , wherein the subsequence length corresponds to the length of a subsequence in the time series.

17. The server computer of claim 14 , wherein generating the approximate matrix profile comprises using an inter-similarity join matrix profile between the plurality of subsequence matrix profiles.

18. The server computer of claim 14 , wherein generating the plurality of subsequence matrix profiles includes applying the subset of subsequences in the dictionary to the time series.

Assignees

• Visa Int Service Ass

Inventors

• Yeh Michael
• Zheng Yan
• Wang Junpeng
• Zhang Wei
• Zhuang Zhongfang

Classifications

• G06F16/2477

  Temporal data queries · CPC title

• G06F16/2465

  Query processing support for facilitating data mining operations in structured databases · CPC title

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F2218/16

  by matching signal segments · CPC title

• G06F16/24537 Primary

  of operators · CPC title