[数学]Indexing Time Series.ppt

Indexing Time Series Time Series Databases A time series is a sequence of real numbers, representing the measurements of a real variable at equal time intervals Stock prices Volume of sales over time Daily temperature readings ECG data A time series database is a large collection of time series Time Series Data Time Series Problems (from a database perspective) The Similarity Problem X = x1, x2, …, xn and Y = y1, y2, …, yn Define and compute Sim(X, Y) E.g. do stocks X and Y have similar movements? Retrieve efficiently similar time series (Indexing for Similarity Queries) Types of queries whole match vs sub-pattern match range query vs nearest neighbors all-pairs query Examples Find companies with similar stock prices over a time interval Find products with similar sell cycles Cluster users with similar credit card utilization Find similar subsequences in DNA sequences Find scenes in video streams Problems Define the similarity (or distance) function Find an efficient algorithm to retrieve similar time series from a database (Faster than sequential scan) Metric Distances What properties should a similarity distance have to allow (easy) indexing? D(A,B) = D(B,A) Symmetry D(A,A) = 0 Constancy of Self-Similarity D(A,B) = 0 Positivity D(A,B) ? D(A,C) + D(B,C) Triangular Inequality Some times the distance function that best fits an application is not a metric… then indexing becomes interesting…. Euclidean Similarity Measure View each sequence as a point in n-dimensional Euclidean space (n = length of each sequence) Define (dis-)similarity between sequences X and Y as Euclidean model Advantages Easy to compute: O(n) Allows scalable solutions to other problems, such as indexing clustering etc... Dynamic Time Warping[Berndt, Clifford, 1994] Allows acceleration-deceleration of signals along the time dimension Basic idea Consider X = x1, x2, …, xn , and Y = y1, y2, …, yn We are allowed to extend each sequence by repeating elements Euclidean