Patent US5940825A successfully refreshed from Google Patents.
US5940825A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive similarity searching in sequence databases
Assignee: International Business Machines Corp
•
Filing: 1996-10-04
•
Granted: 1999-08-17
•
Expires: 2016-10-04
Abstract
Abstract A computer system and method for performing similarity searches which is phase and scale insensitive and which allows similarity searches to be performed at a semantic level. Each sequence in a database is preferably segmented at multiple projections and/or resolution levels. The sequences may represent object having multi-dimensional features such as temporal and/or spatial-temporal data. Preferably, the segmenting logic starts with the finest resolution, and each sequence is parsed into a number of disjointed segments, wherein each segment has uniform features. The uniform features could be segments having a constant slope, or waveform segments representable by a single function. The segments may then be re-sampled into a fixed length vector with appropriate normalization. A label may also be assigned to each segment via conventional clustering/classification methods. The above steps are iterated at successive projections and/or resolution levels until each sequence in the database has been independently segmented and clustered. Thus, the labels are preferably extracted in a pseudo-hierarchical manner in which the label of the lowest resolution representation of the sequence is extracted first. The representation of each time series at various resolutions and/or projections captures different characteristics of the same time series (or 2D/3D objects). Recall that each segment represents a region having uniform features. The segmentation at each individual resolution and/or projection thus enables recognition or emphasis of different characteristics within segments having uniform features.
Inventors
- 👤 Vittorio Castelli
- 👤 Chung-Sheng Li
- 👤 Philip Shi-lung Yu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:43
CPC Classifications
G; G01; G01V; G01V1/00; G01V1/28; G01V1/288; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99936; Y10S707/99937
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
66 words
A computerized method of indexing data sequences for similarity pattern matching, comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of a plurality of stored sequences; segmenting the sequences at said one or more of multiple resolutions and projections, wherein each sequence segment has uniform features; and storing sequence segments in a computer readable memory.
Claim 2
Dependent Claim
66 words
A computerized method of indexing data sequences for similarity pattern matching, comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of a plurality of stored sequences; segmenting the sequences at said one or more of multiple resolutions and projections, wherein each sequence segment has uniform features; and storing sequence segments in a computer readable memory.
Claim 3
Dependent Claim
27 words
The method of claim 1, further comprising the steps of: normalizing said each sequence segment; and classifying said each sequence segment, in response to said normalizing step.
Claim 4
Dependent Claim
30 words
The method of claim 1, wherein said storing step comprises the step of storing each sequence segment into a hierarchy of said one or more of multiple resolutions and projections.
Claim 5
Dependent Claim
24 words
The method of claim 2 wherein said generating step comprises the step of transforming the sequences by one of sub-band filtering and wavelet transformation.
Claim 6
Dependent Claim
22 words
The method of claim 2, wherein said classifying step comprises the step of classifying said each sequence segment at progressively higher resolutions.
Claim 7
Dependent Claim
45 words
The method of claim 2, further comprising the steps of: optimizing sequence segment clusters by iteratively refining said segmentation step; evaluating the clusters, in response to each iterative refinement; and selecting an iterative refinement having an optimal clustering performance, in response to said evaluating step.
Claim 8
Dependent Claim
20 words
The method of claim 1 wherein the sequences represent objects having multi-dimensional features including one of temporal and spatial-temporal data.
Claim 9
Dependent Claim
90 words
The method of claim 2, further comprising a genetic method for clustering classified segments, comprising the steps of: said segmenting step including the step of generating a seed segmentation, wherein the seed segmentation represents an initial constellation of a cluster centroid; generating multiple perturbations of the seed segmentation by adding a randomly generated vector having an increased magnitude to each cluster centroid; said step of classifying sequence segments is performed for each perturbation; evaluating the clusters, classified for said each perturbation; and selecting the perturbation having an optimal clustering performance.
Claim 10
Dependent Claim
39 words
The method of claim 8, wherein said evaluating step includes the step of comparing a gain in clustering performance with a predetermined threshold; and terminating said step of generating multiple perturbations when the gain does not exceed the threshold.
Claim 11
Dependent Claim
42 words
The method of claim 2, wherein said classifying step includes the step of generating labels corresponding to a clustering vocabulary, said method further comprising the step of executing a query using the clustering vocabulary against the sequence segments stored in the memory.
Claim 12
Dependent Claim
28 words
The method of claim 1 wherein said generating step comprises the step of first generating a dominant projection for maximizing a capture of different characteristics of the sequences.
Claim 13
Dependent Claim
96 words
The method of claim 1, for detecting a similarity between a template sequence corresponding to a query and at least one sequence segment stored in the memory, comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of the template sequence; segmenting the template sequence at a plurality of said one or more of multiple resolutions and projections, wherein each template sequence segment has uniform features; and selecting and retrieving the sequence segment stored in the memory having similar causality relationships as a template sequence segment.
Claim 14
Dependent Claim
41 words
The method of claim 12 wherein said selecting step comprises the steps of: progressively searching from a lowest resolution level to a highest resolution level; and, filtering by combining higher resolution search results only which match lower level resolution search results.
Claim 15
Dependent Claim
14 words
A computer database comprising the classified sequences generated by the method of claim 1.
Claim 16
Independent Claim
111 words
A method of detecting a similarity between a query sequence and one or more data sequences stored in a database, wherein the data sequences have been segmented at one or more of multiple resolutions and projections, the method comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of the query sequence; segmenting the query sequence into a series of high-level objects, wherein each query sequence segment has uniform features; progressively searching the database and retrieving a data sequence segment stored in the memory having similar causality relationships as a query sequence segment; and combining matching segments and scoring combined sequences.
Claim 17
Independent Claim
111 words
A method of detecting a similarity between a query sequence and one or more data sequences stored in a database, wherein the data sequences have been segmented at one or more of multiple resolutions and projections, the method comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of the query sequence; segmenting the query sequence into a series of high-level objects, wherein each query sequence segment has uniform features; progressively searching the database and retrieving a data sequence segment stored in the memory having similar causality relationships as a query sequence segment; and combining matching segments and scoring combined sequences.
Claim 18
Dependent Claim
29 words
The method of claim 15 wherein said searching step comprises searching at increasingly higher resolutions only when a match is found at one of a previous resolution and projection.
Claim 19
Dependent Claim
31 words
The method of claim 15, wherein said searching step comprises searching at increasingly higher resolutions; and said combining step comprises the step of combining match results at said increasingly higher resolutions.
Claim 20
Dependent Claim
47 words
The method of claim 15, further comprising the steps of: normalizing and classifying each query sequence segment at said one or more of multiple resolutions and projections; wherein the query sequence comprises a series of symbols from a vocabulary of said classifying step or a template sequence.
Claim 21
Dependent Claim
31 words
The method of claim 15, further comprising the steps of: normalizing and classifying each query sequence segment at said one of multiple resolutions and projections; and searching for similar database segments.
Claim 22
Dependent Claim
86 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for indexing data sequences for similarity pattern matching, said method comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of a plurality of stored sequences; segmenting the sequences at said one or more of multiple resolutions and projections, wherein each sequence segment has uniform features; and storing sequence segments in a computer readable memory.
Claim 23
Dependent Claim
86 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for indexing data sequences for similarity pattern matching, said method comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of a plurality of stored sequences; segmenting the sequences at said one or more of multiple resolutions and projections, wherein each sequence segment has uniform features; and storing sequence segments in a computer readable memory.
Claim 24
Dependent Claim
29 words
The program storage device of claim 20, further comprising the steps of: normalizing said each sequence segment; and classifying said each sequence segment, in response to said normalizing step.
Claim 25
Dependent Claim
32 words
The program storage device of claim 20, wherein said storing step comprises the step of storing each sequence segment into a hierarchy of said one or more of multiple resolutions and projections.
Claim 26
Dependent Claim
26 words
The program storage device of claim 20 wherein said generating step comprises the step of transforming the sequences by one of sub-band filtering and wavelet transformation.
Claim 27
Dependent Claim
25 words
The program storage device of claim 21, wherein said classifying step is comprises the step of classifying said each sequence segment at progressively higher resolutions.
Claim 28
Dependent Claim
47 words
The program storage device of claim 21, further comprising the steps of: optimizing sequence segment clusters by iteratively refining said segmenting step; evaluating the clusters, in response to each iterative refinement; and selecting an iterative refinement having an optimal clustering performance, in response to said evaluating step.
Claim 29
Dependent Claim
22 words
The program storage device of claim 20 wherein the sequences represent objects having multi-dimensional features including one of temporal and spatial-temporal data.
Claim 30
Dependent Claim
92 words
The program storage device of claim 20, further comprising a genetic method for optimizing the clusters, comprising the steps of: said segmenting step including the step of generating a seed segmentation, wherein the seed segmentation represents an initial constellation of a cluster centroid; generating multiple perturbations of the seed segmentation by adding a randomly generated vector having an increased magnitude to each cluster centroid; said step of classifying sequence segments is performed for each perturbation; evaluating the clusters, classified for said each perturbation; and selecting the perturbation having an optimal clustering performance.
Claim 31
Dependent Claim
41 words
The program storage device of claim 26, wherein said evaluating step includes the step of comparing a gain in clustering performance with a predetermined threshold; and terminating said step of generating multiple perturbations when the gain does not exceed the threshold.
Claim 32
Dependent Claim
44 words
The program storage device of claim 21, wherein said classifying step includes the step of generating labels corresponding to a clustering vocabulary, said method further comprising the step of executing a query comparing the clustering vocabulary against the sequence segments stored in the memory.
Claim 33
Dependent Claim
30 words
The program storage device of claim 20 wherein said generating step comprises the step of first generating a dominant projection for maximizing a capture of different characteristics of the sequences.
Claim 34
Dependent Claim
34 words
The program storage device of claim 20, comprising the steps of: segmenting and classifying a template corresponding to a query; and selecting a stored sequence segment having similar causality relationships as a template segments.
Claim 35
Dependent Claim
65 words
The program storage device of claim 31 wherein said step of selecting stored sequences comprises the steps of: transforming each sequence segment into progressively higher sequence resolutions; wherein said segmenting step is performed at each sequence resolution; progressively searching from a lowest resolution level to a highest resolution level; and, filtering by combining higher resolution search results only which match lower level resolution search results.
Claim 36
Dependent Claim
112 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for detecting a similarity between a template sequence corresponding to a query and at least one sequence segment stored in the memory, comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of the template sequence; segmenting the template sequence at a plurality of said one or more of multiple resolutions and projections, wherein each template sequence segment has uniform features; and selecting and retrieving the sequence segment stored in the memory having similar causality relationships as a template sequence segment.
Claim 37
Dependent Claim
112 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for detecting a similarity between a template sequence corresponding to a query and at least one sequence segment stored in the memory, comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of the template sequence; segmenting the template sequence at a plurality of said one or more of multiple resolutions and projections, wherein each template sequence segment has uniform features; and selecting and retrieving the sequence segment stored in the memory having similar causality relationships as a template sequence segment.
Claim 38
Dependent Claim
43 words
The program storage device of claim 33 wherein said selecting step comprises the steps of: progressively searching from a lowest resolution level to a highest resolution level; and, filtering by combining higher resolution search results only which match lower level resolution search results.
Claim 39
Dependent Claim
124 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for detecting a similarity between a query sequence and at least one data sequence stored in a database including data sequences which have been segmented at one of multiple resolutions and projections, the method comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of the query sequence; segmenting the query sequence into a series of high-level objects, wherein each query sequence segment has uniform features; progressively searching the database and retrieving a data sequence segment having similar causality relationships as a query sequence segment; and combining matching segments and scoring combined sequences.
Claim 40
Dependent Claim
124 words
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for detecting a similarity between a query sequence and at least one data sequence stored in a database including data sequences which have been segmented at one of multiple resolutions and projections, the method comprising the steps of: generating representations selected from the group consisting of one or more of multiple resolutions and projections, of the query sequence; segmenting the query sequence into a series of high-level objects, wherein each query sequence segment has uniform features; progressively searching the database and retrieving a data sequence segment having similar causality relationships as a query sequence segment; and combining matching segments and scoring combined sequences.
Claim 41
Dependent Claim
35 words
The program storage device of claim 35, further comprising the steps of: normalizing and classifying each query sequence segment at said one or more of multiple resolutions and projections; and searching for similar database segments.
Claim 42
Dependent Claim
28 words
The program storage device of claim 36, wherein the query comprises one of a template sequence and a series of symbols from a vocabulary of said classifying step.
Claim 43
Dependent Claim
47 words
The program storage device of claim 36, wherein the query includes said template sequence, further comprising the steps of: said segmenting step including segmenting the template sequence at each resolution along multiple projections, wherein each template sequence segment has uniform features; normalizing said each template sequence segment.
Claim 44
Dependent Claim
31 words
The program storage device of claim 35 wherein said searching step comprises searching at increasingly higher resolutions only when a match is found at one of a previous resolution and projection.
References Cited (Backward Citations)
US5329405A
Cited
US5471610A
Cited
US5416892A
Cited
US5546572A
Cited
US5426779A
Cited
US5537586A
Cited
US5544352A
Cited
US5832494A
Cited
US5684999A
Cited
US5497486A
Cited
US5668897A
Cited
US5706497A
Cited
US5799268A
Cited
US5710833A
Cited
US5799301A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-16 | 2003-02-15 | 2003-08-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-16 | 2007-02-15 | 2007-08-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-16 | 2011-02-15 | 2011-08-17 | $7700.00 | Window Closed / Lapsed |