# US 2014/0195474 A1 · Method and system for improved pattern matching > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0195474 A1 - Document ID: US20140195474A1 - Status: Published application - Kind: A1 - Application number: 14/108,656 - Filed: 2013-12-17 - Published: 2014-07-10 - Earliest claimed: 2012-12-18 - Assignees: Telefonica, S.A. - Inventors: Xavier ANGUERA MIRÓ - Web page: https://patentgrep.com/patent/US20140195474A1 ## CPC - G06N 5/047: Pattern matching networks; Rete networks - G10L 15/12: using dynamic programming techniques, e.g. dynamic time warping [DTW] - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING ## Abstract Method, system and computer program for determining matching between two time series. They use an improved algorithm partially based in Dynamic Time Warping and Information Retrieval techniques, but solving the problems (as computational complexity, memory requirements . . . ) observed in these matching techniques. ## Claims ### Claim 1 A computer-implemented method of determining matching subsequences between a first sequence of values and a second sequence of values, said method comprising: inputting said first and second sequences of values into an alignment algorithm, said alignment algorithm defining a plane of points corresponding to said sequences of values, said alignment algorithm identifying similar points on said plane according to a predefined similarity metric, and said alignment algorithm grouping a plurality of said similar points between said two sequence values so as to define a path according to said alignment algorithm, and outputting a series of optimized matching subsequences according to predetermined path characteristic metrics, wherein said alignment algorithm uses a one-dimensional vector structure of paths, and said paths have a non-linear alignment between said matching subsequences. ### Claim 2 (depends on 1) A method according to claim 1 where the first sequence of values is a first time series Q={q1; q2; ; qM} and the second sequence of values is a second time series R={r1; r2; . . . ; rN} of real valued n-dimensional vectors, where n is a design parameter, where said one-dimensional vector structure of paths is called ΔT and is set as void as start up and where said alignment algorithm includes the following steps: a) For every vector, qi, belonging to Q do: b1) Select the vectors in R which are considered most similar to qi according to the predefined similarity metric b2) For every vector rj belonging to the group selected in the previous step do: b21) Set a variable k=trj−tqi, where tqi and tri are the offsets of vector qi and rj from the start of their respective sequences. b22) Set a variable best_path=(qi, rj) b23) For k′=k−Wrange to k+WRange, where Wrange is a design parameter do: b231) Set a variable p=ΔT(k′) b232) Determine if the offset between vector pair (qi, rj) and p is less than a predefined first threshold, and if so, b233) Determine if the vector pair (qi, rj) meets a predefined set of warping constraints with respect to p and if so, b234) Select the best path according to a first path characteristic metric, between the path composed by adding the vector pair (qi, rj) to p and the path stored in best_path and set the variable best_path as the path selected b235) Go to step b231) for the next value of k′ b24) ΔT(k)=best_path b25) Go to step b21) for the next value of rj b3) Go to step b2) for the next value of qi ### Claim 3 (depends on 2) A method according to claim 2 where the method further comprises a step c), comprising: for all the paths registered in ΔT, calculate a second path characteristic metric and including in a set of optimal paths, only the paths whose second path characteristic metrics meet a predefined criteria. ### Claim 4 (depends on 3) A method according to claim 3, where the first and the second path characteristic metrics are selected from one of the following: the number of points in the path, the accumulated distance of the points in the path, average similarity of the points in the path, path length or a combination of these criteria. ### Claim 5 (depends on 3) A method according to claim 3, where the method further comprises a step d) comprising: when a path is selected to be included in the set of optimal paths, checking if there is any path already included in said set in strong overlap with the new one, and if so, merging the new path with the path found to obtain a merged path and instead of including the selected path, including the merged path in the set of optimal paths and deleting the path found in strong overlap with the new one from the set of optimal paths. ### Claim 6 (depends on 2) A method according to claim 2, where if the offset between vector pair (qi, rj) and p is not less than the predefined first threshold, the second path characteristic metric is calculated for path p and said path is included in the a set of optimal paths if its path characteristic metric met the predefined criteria. ### Claim 7 (depends on 2) A method according to claim 2 where the step of selecting the vectors in R which are considered most similar to qi according to the predefined similarity metric, comprises: calculate the predefined similarity metric between qi and each of the vectors of R and selects said vectors of R whose predefined similarity metric with qi is less than a predefined second threshold and where the predefined similarity metric is the Euclidean distance, the inner product or any other distance or similarity between vectors. ### Claim 8 (depends on 2) A method according to claim 2 where the step of selecting the vectors in R which are considered most similar to qi according to the predefined similarity metric is performed using an Information Retrieval based algorithm to allow fast retrieval of similar vectors, like for example the Locality Sensitive Hashing algorithm. ### Claim 9 (depends on 2) A method according to claim 2, where the step of determining if the offset between vector pair (qi, rj) and p is less than a predefined first threshold, called maxQDist, comprises: determining if trj-p·trend=0 and tqi−tqend>=0, where p·tqend and p·trend are the offsets of points qend and rend from the start of their respective sequences and rend, qend is the last matching point of the path p. ### Claim 11 (depends on 2) A method according to claim 2, where the step of determining if the vector pair (qi, rj) meets a predefined set of warping constraints with respect to p, comprises: determining if tqi−tqend>=(trjp·trend)/2 and tqi−qend<=2*(trj−p·trend), where p·tqend and p·trend are the offsets of points qend and rend from the start of their respective sequences and rend, qend is the last matching point of the path p. ### Claim 12 (depends on 2) A method according to claim 2, where the vector ΔT is implemented as a circular buffer of length L, where the path in position k will be stored in ΔT in location l, where l is the remainder from the division of k by L. ### Claim 13 (depends on 2) A method according to claim 2 where the offset is a time offset. ### Claim 14 (depends on 1) A system comprising means adapted to perform the method according to claim 1. ### Claim 15 (depends on 1) A computer program comprising computer program code means adapted to perform the method according to claim 1 when said program is run on a computer, a digital signal processor, a field-programmable gate array, an application-specific integrated circuit, a micro-processor, a micro-controller, or any other form of programmable hardware.