A data-adaptive and dynamic segmentation index for whole matching on time series

Abstract

Similarity search on time series is an essential operation in manyapplications. In the state-of-the-art methods, such as the R-treebased methods, SAX and iSAX, time series are by default dividedinto equi-length segments globally, that is, all time series are segmentedin the same way. Those methods then focus on how toapproximate or symbolize the segments and construct indexes. Inthis paper, we make an important observation: global segmentationof all time series may incur unnecessary cost in space and time forindexing time series. We develop DSTree, a data adaptive and dynamicsegmentation index on time series. In addition to savings inspace and time, our new index can provide tight upper and lowerbounds on distances between time series. An extensive empiricalstudy shows that our new index DSTree supports time series similaritysearch effectively and efficiently. © 2013 VLDB Endowment.