L-Match: A Lightweight and Effective Subsequence Matching Approach

Abstract

Many IoT (Internet of Things) applications, like the industrial internet and the smart city, collect data continuously from massive sensors. It is crucial to exploit and analyze the time series data efficiently. Subsequence matching is a fundamental task in mining time series data. Most existing works develop the index and the matching approach for the static time series data. However, IoT applications need to continuous collect new data and deposit huge historical time series data, which pose a significant challenge for the static indexing approach. To address this challenge, we propose a lightweight index structure, L-index, and a matching approach, L-match, for the constraint normalized subsequence matching problem (cNSM). L-index is a two-layer structure and built on the simple series synopsis, the mean values of the disjoint windows. It is easy to build and update as data grows. Moreover, to further improve the efficiency for the variable query lengths, an optimization technique, named SD-pruning, is proposed. We conduct extensive experiments, and the results verify the effectiveness and efficiency of the proposed approach.

Keywords

• Time series
• subsequence matching
• normalization
• index