ADAPTIVE SIMILARITY SEARCHING IN SEQUENCE DATABASES

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.