Fast Subsequence Matching in Time-Series Databases

Fast Subsequence Matching in Time-Series Databases

T.R. 93-86 | C. Faloutsos, M. Ranganathan, and Y. Manolopoulos
The paper presents an efficient indexing method for locating subsequences within a collection of sequences that match a given query pattern within a specified tolerance. The method involves mapping each data sequence into a small set of boxes in feature space, which can be indexed using spatial access methods like the R*-tree. The authors propose an algorithm to divide these trails into sub-trails, represented by their Minimum Bounding Rectangles (MBRs), and handle queries of varying lengths. Experiments on synthetic and real data (stock price movements) show that the method significantly reduces search time compared to sequential scanning, achieving up to 100 times improvement. The method is designed to be fast, correct, space-efficient, dynamic, and handle sequences of varying lengths. Future work includes extending the method to 2-dimensional grayscale images and n-dimensional vector fields.The paper presents an efficient indexing method for locating subsequences within a collection of sequences that match a given query pattern within a specified tolerance. The method involves mapping each data sequence into a small set of boxes in feature space, which can be indexed using spatial access methods like the R*-tree. The authors propose an algorithm to divide these trails into sub-trails, represented by their Minimum Bounding Rectangles (MBRs), and handle queries of varying lengths. Experiments on synthetic and real data (stock price movements) show that the method significantly reduces search time compared to sequential scanning, achieving up to 100 times improvement. The method is designed to be fast, correct, space-efficient, dynamic, and handle sequences of varying lengths. Future work includes extending the method to 2-dimensional grayscale images and n-dimensional vector fields.
Reach us at info@study.space