Adaptive similarity searching in sequence databases

Details Adaptive similarity searching in sequence databases Adaptive similarity searching in sequence databases

1996-10-04

1999-08-17

Black, Thomas G.

Data processing: database and file management or data structures

Database design

Data structure types

707 2, 707 3, 707 7, G06F 1730

Patent

active

059408251

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.

REFERENCES:
patent: 5329405 (1994-07-01), Hou et al.
patent: 5416892 (1995-05-01), Loken-Kim
patent: 5426779 (1995-06-01), Chambers, IV
patent: 5471610 (1995-11-01), Kawaguchi et al.
patent: 5497486 (1996-03-01), Stolfo et al.
patent: 5537586 (1996-07-01), Amram et al.
patent: 5544352 (1996-08-01), Egger
patent: 5546572 (1996-08-01), Seto et al.
patent: 5668897 (1997-09-01), Stolfo
patent: 5684999 (1997-11-01), Okamoto
patent: 5706497 (1998-01-01), Takahashi et al.
patent: 5710833 (1998-01-01), Moghaddam et al.
patent: 5799268 (1998-08-01), Boguraev
patent: 5799301 (1998-08-01), Castelli et al.
patent: 5832494 (1998-11-01), Egger et al.
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.
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.

Affiliated with

Also associated with

Rating

Adaptive similarity searching in sequence databases does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Adaptive similarity searching in sequence databases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive similarity searching in sequence databases will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-325772