Patent US7103222B2 successfully refreshed from Google Patents.
US7103222B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pattern discovery in multi-dimensional time series using multi-resolution matching
Assignee: Mitsubishi Electric Research Laboratories Inc
•
Filing: 2002-11-01
•
Granted: 2006-09-05
•
Expires: 2022-11-01
Abstract
Abstract A method discovers patterns in unknown multi-dimensional data. A time-series of the multi-dimensional data is generated and a point cross-distance matrix is constructed by self-correlating the time-series. All minimum cost paths in the point cross-distance matrix are located at multiple time resolutions. The minimum cost paths are then related to temporal sub-sequences in the multi-dimensional data to discover high-level patterns in the unknown multi-dimensional data.
Inventors
- 👤 Kadir A. Peker
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:11
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/70; G06F16/78; G06F16/783; G06F16/7847; G06F16/785; G06F16/73; G06F16/738; G06F16/739; G06F16/7834; G06F16/7857; G06F16/786
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
67 words
A computerized method for discovering patterns in unknown multi-dimensional data, comprising: generating a time series of the unknown multi-dimensional data; constructing a point cross-distance matrix by self-correlating the time series; locating all minimum cost paths in the point cross-distance matrix at a plurality of time resolutions; and relating the minimum cost paths to sub-sequences in the times series to discover high-level patterns in the unknown multi-dimensional data.
Claim 2
Dependent Claim
67 words
A computerized method for discovering patterns in unknown multi-dimensional data, comprising: generating a time series of the unknown multi-dimensional data; constructing a point cross-distance matrix by self-correlating the time series; locating all minimum cost paths in the point cross-distance matrix at a plurality of time resolutions; and relating the minimum cost paths to sub-sequences in the times series to discover high-level patterns in the unknown multi-dimensional data.
Claim 3
Dependent Claim
19 words
The method of claim 1 wherein the time series data is generated from selected features of the multi-dimensional data.
Claim 4
Dependent Claim
11 words
The method of claim 1 wherein the time series is thresholded.
Claim 5
Dependent Claim
12 words
The method of claim 1 wherein the point-cross distance matrix is filtered.
Claim 6
Dependent Claim
16 words
The method of claim 1 wherein the unknown multi-dimensional data are unknown content of a video.
Claim 7
Dependent Claim
19 words
The method of claim 1 wherein the unknown multi-dimension data is partitioned into clusters according to the high-level patterns.
Claim 8
Dependent Claim
23 words
The method of claim 1 wherein all of the minimum cost paths are located at multiple temporal resolutions using windows of size w.
Claim 9
Dependent Claim
127 words
The method of claim of claim 7 wherein a distance in the point cross-distance matrix for two windows of the size w is D w ( x i , x j ) = ∑ k = 0 w - 1 ( x i + k - x j + k ) 2 , and D 1 ( x i , x j ) = ( x i + k - x j + k ) 2 , and D w ( x i , x j ) = ∑ k = 0 w - 1 D 1 ( x i + k , x j + k ) , where x i and x j are end points of the window.
Claim 10
Dependent Claim
31 words
The method of claim 8 wherein all of the minimum cost paths are located by searching the point cross-distance matrix for diagonal line segments of distances less than a predetermined threshold.
Claim 11
Dependent Claim
24 words
The method of claim 1 wherein all of the minimum cost paths are substantially parallel to a major diagonal of the point cross-distance matrix.
Claim 12
Dependent Claim
19 words
The method of claim 7 wherein the multiple temporal resolutions are obtained by sub-sampling the time series using multi-scaling.
Claim 13
Dependent Claim
10 words
The method of claim 11 wherein the scaling uses wavelets.
Claim 14
Dependent Claim
24 words
The method of claim 1 wherein dynamic time warping is applied to the time series to stretch and compress time in the time series.
Claim 15
Dependent Claim
21 words
The method of claim 1 further comprising: applying dynamic programming to find optimum minimum cost paths in the point cross-distance matrix.
Claim 16
Dependent Claim
17 words
The method of claim 1 further comprising: only processing an upper half of the point cross-distance matrix.
Claim 17
Dependent Claim
23 words
The method of claim 1 further comprising: merging any minimum cost paths whose end points are within a predetermine distance of each other.
Claim 18
Dependent Claim
21 words
The method of claim 1 further comprising: merging any minimum cost paths where one path is a superset of another path.
Claim 19
Dependent Claim
17 words
The method of claim 1 further comprising: eliminating any minimum distance path shorter then a predetermined length.
Claim 20
Dependent Claim
13 words
The method of claim 1 wherein the multi-dimensional data is a speech signal.
Claim 21
Dependent Claim
13 words
The method of claim 1 wherein the multi-dimensional data is a linear polymer.
Claim 22
Dependent Claim
12 words
The method of claim 20 wherein the linear polymer is a protein.
Claim 23
Dependent Claim
12 words
The method of claim 16 wherein the merging uses a Hough transform.
Claim 24
Dependent Claim
24 words
The method of claim 1 further comprising: applying an edge detector to the point cross-distance matrix to find all of the minimum cost paths.
References Cited (Backward Citations)
US4718093A
Cited
US4982438A
Cited
US5341437A
Cited
US5638460A
Cited
US6014626A
Cited
US6067369A
Cited
US6369835B1
Cited
US6477515B1
Cited
US20010036304A1
Cited
US6665852B2
Cited
US20030001862A1
Cited
US20030177112A1
Cited
US20030190060A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-09-04 | 2010-03-06 | 2010-09-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-09-04 | 2014-03-06 | 2014-09-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-09-04 | 2018-03-06 | 2018-09-05 | $7700.00 | Window Closed / Lapsed |