An Efficient Index Structure for Shift and Scale Invariant Search of Multi-Attribute Time Sequence

We investigate the problem of searching similar multi-attribute time sequences in databases. Such sequences arise naturally in a number of medical, financial, video, weather forecast, and stock market databases where more than one attribute is of interest at a time instant. We formulate a new symmetric scale and shift invariant notion of distance for such sequences. We also propose a new index structure that transforms the data sequences and clusters them according to their shiftings and scalings. This clustering improves the efficiency considerably. According to our experiments with real and synthetic datasets, the index structure's performance is 5 to 60 times better than competing techniques, the exact speedup based on other optimizations such as caching and replication. Finally, we also consider the subsequence search problem.