KV-match: A Subsequence Matching Approach
Supporting Normalization and Time Warping
Jiaye Wu
#
, Peng Wang
#
, Ningting Pan
#
, Chen Wang
∗
, Wei Wang
#
, Jianmin Wang
∗
#
School of Computer Science, Fudan University, Shanghai, China
{wujy16, pengwang5, ntpan17, weiwang1}@fudan.edu.cn
∗
School of Software, Tsinghua University, Beijing, China
{wang_chen, jimwang}@tsinghua.edu.cn
Abstract—The volume of time series data has exploded due
to the popularity of new applications, such as data center
management and IoT. Subsequence matching is a fundamental
task in mining time series data. All index-based approaches only
consider raw subsequence matching (RSM) and do not support
subsequence normalization. UCR Suite can deal with normalized
subsequence matching problem (NSM), but it needs to scan
full time series. In this paper, we propose a novel problem,
named constrained normalized subsequence matching problem
(cNSM), which adds some constraints to NSM problem. The
cNSM problem provides a knob to flexibly control the degree
of offset shifting and amplitude scaling, which enables users to
build the index to process the query. We propose a new index
structure, KV-index, and the matching algorithm, KV-match.
With a single index, our approach can support both RSM and
cNSM problems under either ED or DTW distance. KV-index is
a key-value structure, which can be easily implemented on local
files or HBase tables. To support the query of arbitrary lengths,
we extend KV-match to KV-match
DP
, which utilizes multiple
varied-length indexes to process the query. We conduct extensive
experiments on synthetic and real-world datasets. The results
verify the effectiveness and efficiency of our approach.
I. INTRODUCTION
Time series data are pervasive across almost all human
endeavors, including medicine, finance and science. In conse-
quence, there is an enormous interest in querying and mining
time series data [1], [2].
Subsequence matching problem is a core subroutine for
many time series mining algorithms. Specifically, given a long
time series X, for any query series Q and a distance threshold
ε, the subsequence matching problem finds all subsequences
from X, whose distance with Q falls within the threshold ε.
FRM [3] is the pioneer work of subsequence matching.
Many approaches have been proposed, either to improve the
efficiency [4], [5] or to deal with various distance functions [6],
[7], such as Euclidean distance and Dynamic Time Warping.
However, all these approaches only consider the raw subse-
quence matching problem (RSM for short). In recent years,
researchers realize the importance of the subsequence normal-
ization [8]. It is more meaningful to compare the z-normalized
subsequences, instead of the raw ones. UCR Suite [8] is the
The work is supported by the Ministry of Science and Tech-
nology of China, National Key Research and Development Program
(No.2016YFB1000700), NSFC(61672163, U1509213), Shanghai Innovation
Action Project (No.16DZ1100200)
(c) Information of Q
Offset [Label] Length
877 [Q] 17,124
(d) Results of NSM
Offset [Label] Distance
252,492 [S
6
] 117.78
(a) PAMAP time series 97,458
[S
4
] 130.80
0 5000 10000 15000
-5
0
5
10
34,562 [S
3
] 138.12
161,416
[S
5
] 149.37
··· ···
134,456
[S
1
] 164.88
296,063
[S
2
] 166.74
··· ···
(b) Aligned normalized subsequences ε= 200.0
Fig. 1. Illustrative example of cNSM
state-of-the-art approach to solve the normalized subsequence
matching problem (NSM for short).
The NSM approach suffers from two drawbacks. First, it
needs to scan the full time series X, which is prohibitively
expensive for long time series. For example, for a time series
of length 10
9
, UCR Suite needs more than 100 seconds to
process a query of length 1,000. [8] analyzed the reason why it
is impossible to build the index for the NSM problem. Second,
the NSM query may output some results not satisfying users’
intent. The reason is that NSM fully ignores the offset shifting
and amplitude scaling. However, in real world applications, the
extent of offset shifting and amplitude scaling may represent
certain specific physical mechanism or state. Users often only
hope to find subsequences within similar state as the query.
We illustrate it with an example.
Example 1. The time series in Fig. 1(a) comes from the
Physical Activity Monitoring for Aging People (PAMAP)
dataset [1] collected from z-accelerometer at hand position.
The monitored person conducts various activities alternatively,
like sitting, standing, running and so on. Each activity lasts for
about 3 minutes, and the data collection frequency is 100Hz.
We use one subsequence corresponding to lying activity as
the query (Q in Fig. 1(c)) to find other “lying” subsequences.
We issue a NSM query with Q, and Fig. 1(d) lists the top
results. Unfortunately, all top-4 results corresponds to other
activities. S
3
and S
5
correspond to sitting activity, while S
4
and S
6
correspond to breaking activity. Although S
1
and S
2
866
2019 IEEE 35th International Conference on Data Engineering (ICDE)
2375-026X/19/$31.00 ©2019 IEEE
DOI 10.1109/ICDE.2019.00082
剩余11页未读，继续阅读
资源评论
