Constructing Compact Time Series Index for Efficient Window Query Processing

Zhao，Jing1; Wang，Peng1; Tang，Bo2; Liu，Lu1; Wang，Chen3; Wang，Wei1; Wang，Jianmin3

10.1109/ICDE53745.2022.00272

2022

38th IEEE International Conference on Data Engineering (ICDE)

1084-4627

978-1-6654-0884-4

Proceedings - International Conference on Data Engineering

2022-May

3025-3037

9-12 May 2022

Kuala Lumpur, Malaysia

10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA

IEEE COMPUTER SOC

Analyzing and mining of time series have been widely studied in both academia and industry in recent years. Given a set of long time series, data analysts can utilize the window-based similarity search to explore subsequences in arbitrary time windows. Existing techniques are not efficient for window-based query processing. In particular, the whole matching index approach needs to build an individual index for each window, which incurs huge space cost. The existing window-based approach can only cluster neighboring windows, which leads to loose bounds of each group, and thus degrades the query processing efficiency. In this paper, we propose a compact time series index (WinIdx) for efficient window query processing. Specifically, i) we propose a novel distance measurement to capture the similarity between windows, ii) WinIdx provides a compact index structure for windows within a cluster by exploiting the similarity among subsequences relationships, and iii) several optimizations (e.g., sortable summarization, summarization envelop) are equipped in WinIdx to improve the efficiency of index construction, query processing and index footprints. We conduct extensive experiments on both real and synthetic time series to demonstrate the superiority of WinIdx against state-of-the-art approaches.

Industries Query processing Time series analysis Buildings Data engineering Distance measurement Windows

Others

English

CPCI-S ; EI

National Key Research and Development Program[2020YFB1710001]

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Information Systems ; Computer Science, Theory & Methods

WOS:000855078403007

20223512637613

Efficiency ; Time series

Production Engineering:913.1 ; Mathematical Statistics:922.2

2-s2.0-85136399310

Scopus

1.School of Computer Science,Fudan University,China
2.Southern University of Science and Technology,Department of Computer Science and Engineering,China
3.Nelbds,Eiri,School of Software,Tsinghua University,China

Zhao，Jing,Wang，Peng,Tang，Bo,et al. Constructing Compact Time Series Index for Efficient Window Query Processing[C]. 10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA:IEEE COMPUTER SOC,2022:3025-3037.