期刊
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
卷 25, 期 6, 页码 1425-1438出版社
IEEE COMPUTER SOC
DOI: 10.1109/TKDE.2012.88
关键词
Time series; similarity measures; similarity search; distance metrics
类别
资金
- US National Science Foundation [IIS-0705749, IIS-0812601, IIS-1055062, CNS-0923494, CNS-1035913, CNS-0915834, III-1018865]
- UTA startup grant
- UTA STARS awards
- NHARP grant, Texas Higher Education Coordinating Board
- Microsoft Research
- Nokia Research
- Div Of Information & Intelligent Systems
- Direct For Computer & Info Scie & Enginr [1055062] Funding Source: National Science Foundation
A novel metric for time series, called Move-Split-Merge (MSM), is proposed. This metric uses as building blocks three fundamental operations: Move, Split, and Merge, which can be applied in sequence to transform any time series into any other time series. A Move operation changes the value of a single element, a Split operation converts a single element into two consecutive elements, and a Merge operation merges two consecutive elements into one. Each operation has an associated cost, and the MSM distance between two time series is defined to be the cost of the cheapest sequence of operations that transforms the first time series into the second one. An efficient, quadratic-time algorithm is provided for computing the MSM distance. MSM has the desirable properties of being metric, in contrast to the Dynamic Time Warping (DTW) distance, and invariant to the choice of origin, in contrast to the Edit Distance with Real Penalty (ERP) metric. At the same time, experiments with public time series data sets demonstrate that MSM is a meaningful distance measure, that oftentimes leads to lower nearest neighbor classification error rate compared to DTW and ERP.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据