Grant: Discovery Grants Program - Individual

Researchers work over increasingly large distributed data sets. Literary researchers have access to most classical works in digital format. There are terabytes of biological data freely available on the Web. Sequential data such as text or time series is common and has been identified as an area of critical importance by the database research community. Mining patterns in terabytes of time series or text with user-driven techniques, is an important open problem. We want to provide tools to users so that they can interactively aggregate sequential data into views, as in On-Line Analytical Processing (OLAP). To do so, we need well adapted hierarchies over the data so that drill-down and roll-up queries can be supported. We need robust time series indexing. Finally, we need a good model for sequential databases: should we complement existing information retrieval tools or extend current databases? In either case, the amount of data is so large that we need good strategies to preaggregate the data. In OLAP, attribute values are aggregated by star schema hierarchies (store/city/province, client ID/age group). Words can be aggregated in phrases, sentences and paragraphs or by hyponymy (car/vehicle) though there are issues with word sense disambiguation. An equivalent for time series is segmentation. Segmentation divides the data into intervals where it behaves approximately according to a simple model (e.g. constant, linear, quadratic, unimodal, monotonic, convex). Segmentation is a hierarchical process since intervals can be further subdivided. Recently, some progress has been made in time warping indexing. When comparing two time series, time warping locally accelerates or slows time in one time series to compute robust similarity measures.