 |
|
|
|
|
|
 Title: |
US5940825:
Adaptive similarity searching in sequence databases
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Castelli, Vittorio; White Plains, NY
Li, Chung-Sheng; Ossining, NY
Yu, Philip Shi-lung; Chappaqua, NY
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1999-08-17
/ 1996-10-04
|
| Application Number: |
US1996000726889
|
| IPC Code: |
Advanced:
G01V 1/28;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G01V1/28D;
|
| U.S. Class: |
Current:
707/006;
707/002;
707/003;
707/007;
Original:
707/006;
707/002;
707/003;
707/007;
|
| Field of Search: |
707/006,2,3,4,5,7
|
| Priority Number: |
| 1996-10-04 |
US1996000726889 |
|
| 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.
|
| Attorney, Agent or Firm: |
Jordan, Kevin M. ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Coby, Frantz
|
| INPADOC Legal Status: |
Show legal status actions
|
| Parent Case: |
CROSS-REFERENCE TO RELATED APPLICATIONS
The present invention is related to U.S. patent application Ser. No. 08/513,583, entitled "Apparatus and Method for Performing Adaptive Similarity Searching in a Sequence Database," by V. Castelli et al., filed Aug. 10, 1995, now U.S. Pat. No. 5,799,301. The present invention has a common assignee with this copending patent application which is hereby incorporated by reference in its entirety.
|
| Family: |
None
|
First Claim:
Show all 39 claims |
What is claimed is:
1. 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.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 31 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| U.S. References: |
Go to Result Set:
All U.S. references
| Forward references (31)
|
Backward references (15)
|
Citation Link
Buy
PDF |
Patent |
Pub.Date |
Inventor |
Assignee |
Title |
 |
US5329405 |
1994-07 |
Hou et al. |
Codex Corporation |
Associative cam apparatus and method for variable length string matching
|
|
|
US5416892 |
1995-05 |
Loken-Kim |
Fujitsu Limited |
Best first search considering difference between scores
|
|
|
US5426779 |
1995-06 |
Chambers, IV |
Salient Software, Inc. |
Method and apparatus for locating longest prior target string matching current string in buffer
|
|
|
US5471610 |
1995-11 |
Kawaguchi et al. |
Hitachi, Ltd. |
Method for character string collation with filtering function and apparatus
|
|
|
US5497486 |
1996-03 |
Stolfo et al. |
Stolfo; Salvatore J. |
Method of merging large databases in parallel
|
|
|
US5537586 |
1996-07 |
Amram et al. |
Individual, Inc. |
Enhanced apparatus and methods for retrieving and selecting profiled textural information records from a database of defined category structures
|
|
|
US5544352 |
1996-08 |
Egger |
Libertech, Inc. |
Method and apparatus for indexing, searching and displaying data
|
|
|
US5546572 |
1996-08 |
Seto et al. |
Hitachi, Ltd. |
Method for retrieving database of image information
|
|
|
US5668897 |
1997-09 |
Stolfo |
|
Method and apparatus for imaging, image processing and data compression merge/purge techniques for document image databases
|
|
|
US5684999 |
1997-11 |
Okamoto |
Matsushita Electric Industrial Co., Ltd. |
Apparatus and a method for retrieving image objects based on correlation with natural language sentence parameters
|
|
|
US5706497 |
1998-01 |
Takahashi et al. |
NEC Research Institute, Inc. |
Document retrieval using fuzzy-logic inference
|
|
|
US5710833 |
1998-01 |
Moghaddam et al. |
Massachusetts Institute of Technology |
Detection, recognition and coding of complex objects using probabilistic eigenspace analysis
|
|
|
US5799268 |
1998-08 |
Boguraev |
Apple Computer, Inc. |
Method for extracting knowledge from online documentation and creating a glossary, index, help database or the like
|
|
|
US5799301 |
1998-08 |
Castelli et al. |
International Business Machines Corporation |
Apparatus and method for performing adaptive similarity searching in a sequence database
|
|
|
US5832494 |
1998-11 |
Egger et al. |
Libertech, Inc. |
Method and apparatus for indexing, searching and displaying data
|
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G1999-468572
DERABS G1999-468572
|
| Other References: |
Ronald E. Crochiere et al. "Multirate Digital Signal Processing", Prentice-Hall Signal Processing Series, 5 pages, Title Page and Tabel of Contents, no date.
P. P. Vaidyanathan, "Multirate Digital Filters, Filter Banks, Polyphase Networks, and Applications: A Tutorial", Proceedings of the IEEE, vol.78, No. 1,pp. 56-93, Jan. 1990.
(38 pages)
Cited by 35 patents
Hagit Shatkay et al., "Approximate Queries and Representations for Large Data Sequences", pp. 536-545, IEEE, 1996.
Belur V. Dasarathy, Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques, IEEE Computer Society Press Tutorial, 6 pages. 1991.
C. Faloutsos et al., "Fast Subsequence Matching in Time-Series Databasess", Proc. SIGMOD'94, pp. 419-429, 1994.
|
|
 Nominate this for the Gallery...
|
|
