Fast Subsequence Matching in Time-Series Data bases

Simple item page
dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.authorRanganathan, M.en_US
dc.contributor.authorManolopoulos, Yannisen_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:54:45Z
dc.date.available2007-05-23T09:54:45Z
dc.date.issued1993en_US
dc.description.abstractWe present an efficient indexing method to locate subsequences within a collection of sequences, such that the subsequences match a given (query) pattern within a specified tolerance. The idea is to map each data sequence into a small set of boxes in feature space. Then, these rectangles can be readily indexed using traditional spatial access methods, like the R*-tree [9]. More detailed, we use a sliding window over the data sequence and extract its features; the results is a trail in feature space. We propose an efficient and effective algorithm to divide such trail in sub-trails, which are subsequently represented by their Minimum Bounding Rectangles (MBRs). We also examine queries of varying lengths, and we show how to handle each case efficiently. We implemented our method and carried out experiments on synthetic and real data (stock price movements). We compared the method to sequential scanning, which is the only obvious competitor. The results were excellent: our method accelerated the search time from 3 times up to 100 times.en_US
dc.format.extent974065 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/5430
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1993-86en_US
dc.subjectsignal processingen_US
dc.subjectdatabasesen_US
dc.subjectdata structuresen_US
dc.subjecttelemedicineen_US
dc.subjectSystems Integrationen_US
dc.titleFast Subsequence Matching in Time-Series Data basesen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_93-86.pdf
Size:
951.24 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports