US5799301A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for performing adaptive similarity searching in a sequence database
Assignee: International Business Machines Corp
•
Filing: 1995-08-10
•
Granted: 1998-08-25
•
Expires: 2015-08-10
Abstract
Abstract An apparatus and method includes segmenting each sequence to be stored in a database into nonoverlapping or minimally overlapping subsequences with equal length. Each subsequence is then normalized using a normalization procedure (such as normalized with respect to the energy or maximum amplitude of each sequence) and transformed into a series of coefficients in a feature space. The search is based on hierarchical correlation in the feature space between the target sequence with the subsequences. The correlation between the target sequence and the stored sequences is performed first at the lowest level in the hierarchy. At any given level, a match is declared when the correlated result is larger than a specific threshold. Sequences that fail to satisfy the matching criterion are discarded. The process is continued at the following level until the highest level is reached. Because of the hierarchical search, linear scan of the entire sequence can be avoided.
Inventors
- 👤 Vittorio Castelli
- 👤 Chung Sheng Li
- 👤 Philip Shi-lung Yu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 10:33
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2465; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
141 words
A method for detecting a similarity between a target data sequence and one or more data sequences stored in a database comprising the steps of: retrieving a subset of the stored sequences based on the target sequence and an indexing technique, wherein each of said stored sequences and said target sequence have a numerical value, and wherein each of said stored sequences and said target sequence are stored in a feature space; correlating, based on the numerical values, between said target sequence and said one or more stored sequences at a first level of a predetermined hierarchy in said feature space; testing a result of said correlating step against a predetermined threshold value; declaring a match between said target sequence and said one or more stored sequences if said result of said correlating step is greater than said predetermined threshold value.
Claim 2
Independent Claim
141 words
A method for detecting a similarity between a target data sequence and one or more data sequences stored in a database comprising the steps of: retrieving a subset of the stored sequences based on the target sequence and an indexing technique, wherein each of said stored sequences and said target sequence have a numerical value, and wherein each of said stored sequences and said target sequence are stored in a feature space; correlating, based on the numerical values, between said target sequence and said one or more stored sequences at a first level of a predetermined hierarchy in said feature space; testing a result of said correlating step against a predetermined threshold value; declaring a match between said target sequence and said one or more stored sequences if said result of said correlating step is greater than said predetermined threshold value.
Claim 3
Dependent Claim
71 words
A method, for detecting a similarity between a target data sequence and one or more data sequences stored in a database, according to claim 1, further comprising the step of: repeating said steps of correlating and testing at a next level of said predetermined hierarchy in said feature space if a match is not declared as a result of said testing step executed at a previous level of said predetermined hierarchy.
Claim 4
Independent Claim
78 words
A method for constructing a representation of a database of sequences for detecting a similarity, comprising the steps of: applying a feature extraction function to each of a plurality of stored objects in said database, to create a sequence with reduced dimensions; extracting subsequences having less than a predetermined level of overlapping from the original sequence; normalizing each extracted subsequence; computing metadata for each extacted subsequence; transforming said normalized subsequences; and compressing coefficients of said transformed normalized subsequences.
Claim 5
Independent Claim
78 words
A method for constructing a representation of a database of sequences for detecting a similarity, comprising the steps of: applying a feature extraction function to each of a plurality of stored objects in said database, to create a sequence with reduced dimensions; extracting subsequences having less than a predetermined level of overlapping from the original sequence; normalizing each extracted subsequence; computing metadata for each extacted subsequence; transforming said normalized subsequences; and compressing coefficients of said transformed normalized subsequences.
Claim 6
Dependent Claim
35 words
A method for constructing a representation of a database of sequences for detecting a similarity according to claim 3, further comprising the step of: determining a grouping of said coefficients based on a target sequence.
Claim 7
Dependent Claim
38 words
A method for constructing a representation of a database of sequences for detecting a similarity according to claim 3, further comprising the step of: determining relative importance value for each group of coefficients based on a target sequence.
Claim 8
Dependent Claim
78 words
A method for constructing a representation according to claim 3, further comprising the steps of: normalizing said target sequence; transforming said normalized target sequence; applying a transformed domain convolution between said target sequence and said sequences stored in said database in a feature space; and pruning a set of sequences such that said set of sequences are selected only when the maximum value of the convolution result in a level of the hierarchy is above a predetermined threshold.
Claim 9
Independent Claim
99 words
A method for correlating between a target data sequence and one or more data sequences stored in a database, comprising the steps of: transforming said target sequence into a feature space to generate a first set of coefficients representing said target data sequence in said feature space; computing a first characteristic for each group in a plurality of groups in said target data sequence and said one or more stored data sequences; and ordering each said group in order of said first characteristic to maximize the distinction capability of correlation between said target data sequence and said stored sequence.
Claim 10
Independent Claim
99 words
A method for correlating between a target data sequence and one or more data sequences stored in a database, comprising the steps of: transforming said target sequence into a feature space to generate a first set of coefficients representing said target data sequence in said feature space; computing a first characteristic for each group in a plurality of groups in said target data sequence and said one or more stored data sequences; and ordering each said group in order of said first characteristic to maximize the distinction capability of correlation between said target data sequence and said stored sequence.
Claim 11
Dependent Claim
19 words
A method according to claim 7 wherein said first characteristic is a representation of energy within each said group.
Claim 12
Dependent Claim
19 words
A method according to claim 7 wherein said first characteristic is a measure of variance of each said group.
References Cited (Backward Citations)
US4598385A
Cited
US4700294A
Cited
US5432902A
Cited
US5133052A
Cited
US5049881A
Cited
US5317730A
Cited
US5537586A
Cited
US5450504A
Cited
US5577249A
Cited
US5438628A
Cited
US5706498A
Cited
US5684999A
Cited
US5497486A
Cited
US5668897A
Cited
US5546575A
Cited
US5524240A
Cited
US5485611A
Cited
US5614927A
Cited
US5548755A
Cited
US5710833A
Cited
US5631972A
Cited
US5687190A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-24 | 2002-02-23 | 2002-08-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-24 | 2006-02-23 | 2006-08-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-24 | 2010-02-23 | 2010-08-25 | $7700.00 | Window Closed / Lapsed |