UBC Theses and Dissertations
Multi-scale summaries of temporal trajectories Yang, Ruiyao
Existing studies on time series and temporal trajectories focus on similarity matching and indexing. In this thesis, we argue that for large collections of trajectories, it is useful to provide the functionality of summarization. We envisage a multi-scale framework within which the user is first presented with low-resolution summaries of the underlying trajectories. The user is then allowed to "zoom in" to get high-resolution summaries. We propose two types of summaries: s-summaries and p-summaries. S-summaries are generated based on the probabilistic distribution of the trajectories in the data set, essentially representing the more "typical" trajectories in the data set. In contrast, p-summaries tend to be exhaustive in having every trajectory represented. Both types of summaries rely critically on a summary structure we call a refinement matrix. For s-summaries, a binary tree of 2-dimensional refinement matrices is constructed for multi-scale browsing. For p-summaries, only a single higher-dimensional matrix is needed. Our experimental results show that: (i) the construction of these matrices at compile-time, (ii) the generation of both types of summaries at run-time, and (iii) the refinement of summaries at run-time can all be done efficiently. Finally, we show that the summaries are robust. That is, even if the data set grows significantly, the summaries may not need to be re-computed.
Item Citations and Data