File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Fast and exact warping of time series using adaptive segmental approximations

TitleFast and exact warping of time series using adaptive segmental approximations
Authors
KeywordsNearest neighbor Search
Similarity search
Time series analysis
Issue Date2005
PublisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0885-6125
Citation
Machine Learning, 2005, v. 58 n. 2-3, p. 231-267 How to Cite?
AbstractSimilarity search is a core module of many data analysis tasks including search by example classification and clustering. For time series data Dynamic Time Warping (DTW) has been proven a very effective similarity measure since it minimizes the effects of shifting and distortion in time. However the quadratic cost of DTW computation to the length of the matched sequences makes its direct application on databases of long time series very expensive. We propose a technique that decomposes the sequences into a number of segments and uses cheap approximations thereof to compute fast lower bounds for their warping distances. We present several progressively tighter bounds relying on the existence or not of warping constraints. Finally we develop an index and a multi-step technique that uses the proposed bounds and performs two levels of filtering to efficiently process similarity queries. A thorough experimental study suggests that our method consistently outperforms state-of-the-art methods for DTW similarity search. © 2005 Springer Science + Business Media Inc.
Persistent Identifierhttp://hdl.handle.net/10722/89171
ISSN
2015 Impact Factor: 1.719
2015 SCImago Journal Rankings: 1.753
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorShou, Yen_HK
dc.contributor.authorMamoulis, Nen_HK
dc.contributor.authorCheung, Den_HK
dc.date.accessioned2010-09-06T09:53:16Z-
dc.date.available2010-09-06T09:53:16Z-
dc.date.issued2005en_HK
dc.identifier.citationMachine Learning, 2005, v. 58 n. 2-3, p. 231-267en_HK
dc.identifier.issn0885-6125en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89171-
dc.description.abstractSimilarity search is a core module of many data analysis tasks including search by example classification and clustering. For time series data Dynamic Time Warping (DTW) has been proven a very effective similarity measure since it minimizes the effects of shifting and distortion in time. However the quadratic cost of DTW computation to the length of the matched sequences makes its direct application on databases of long time series very expensive. We propose a technique that decomposes the sequences into a number of segments and uses cheap approximations thereof to compute fast lower bounds for their warping distances. We present several progressively tighter bounds relying on the existence or not of warping constraints. Finally we develop an index and a multi-step technique that uses the proposed bounds and performs two levels of filtering to efficiently process similarity queries. A thorough experimental study suggests that our method consistently outperforms state-of-the-art methods for DTW similarity search. © 2005 Springer Science + Business Media Inc.en_HK
dc.languageengen_HK
dc.publisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0885-6125en_HK
dc.relation.ispartofMachine Learningen_HK
dc.subjectNearest neighbor Searchen_HK
dc.subjectSimilarity searchen_HK
dc.subjectTime series analysisen_HK
dc.titleFast and exact warping of time series using adaptive segmental approximationsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0885-6125&volume=58&issue=2-3&spage=231&epage=267&date=2005&atitle=Fast+and+exact+warping+of+time+series+using+adaptive+segmental+approximationsen_HK
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_HK
dc.identifier.emailCheung, D:dcheung@cs.hku.hken_HK
dc.identifier.authorityMamoulis, N=rp00155en_HK
dc.identifier.authorityCheung, D=rp00101en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s10994-005-5828-3en_HK
dc.identifier.scopuseid_2-s2.0-15544379982en_HK
dc.identifier.hkuros103200en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-15544379982&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume58en_HK
dc.identifier.issue2-3en_HK
dc.identifier.spage231en_HK
dc.identifier.epage267en_HK
dc.identifier.isiWOS:000227474300007-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridShou, Y=8277999000en_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.scopusauthoridCheung, D=34567902600en_HK
dc.identifier.citeulike125682-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats