An Efficient Similarity Searching Algorithm Based on Clustering for Time Series

摘要

Indexing large time series databases is crucial for efficient searching of time series queries. In the paper, we propose a novel indexing scheme RQI (Range Query based on Index) which includes three filtering methods: first-k filtering, indexing lower bounding and upper bounding as well as triangle inequality pruning. The basic idea is calculating wavelet coefficient whose first k coefficients are used to form a MBR (minimal bounding rectangle) based on haar wavelet transform for each time series and then using point filtering method; At the same time, lower bounding and upper bounding feature of each time series is calculated, in advance, and stored into index structure. At last, triangle inequality pruning method is used by calculating the distance between time series beforehand. Then we introduce a novel lower bounding distance function SLBS (Symmetrical Lower Bounding based on Segment) and a novel clustering algorithm CSA (Clustering based on Segment Approximation) in order to further improve the search efficiency of point filtering method by keeping a good clustering trait of index structure. Extensive experiments over both synthetic and real datasets show that our technologies provide perfect pruning power and could obtain an order of magnitude performance improvement for time series queries over traditional naive evaluation techniques.