Title :
HierarchyScan: a hierarchical similarity search algorithm for databases of long sequences
Author :
Li, Chung-Sheng ; Yu, Philip S. ; Castelli, Vittorio
Author_Institution :
IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
fDate :
26 Feb-1 Mar 1996
Abstract :
We present a hierarchical algorithm, HierarchyScan, that efficiently locates one-dimensional subsequences within a collection of sequences of arbitrary length. The subsequences identified by HierarchyScan match a given template pattern in a scale- and phase-independent fashion. The idea is to perform correlation between the stored sequences and the template in the transformed domain hierarchically. Only those subsequences whose maximum correlation value is higher than a predefined threshold will be selected. The performance of this approach is compared to the sequential scanning and an order-of-magnitude speedup is observed
Keywords :
database theory; search problems; string matching; temporal databases; HierarchyScan; data mining; hierarchical similarity search algorithm; long sequence databases; one-dimensional subsequences; spatial-temporal data; stored sequences; Audio databases; Data mining; Feature extraction; Image databases; Indexes; Insurance; Marketing and sales; Multimedia databases; Pattern matching; Spatial databases;
Conference_Titel :
Data Engineering, 1996. Proceedings of the Twelfth International Conference on
Conference_Location :
New Orleans, LA
Print_ISBN :
0-8186-7240-4
DOI :
10.1109/ICDE.1996.492205
