Temporal Dependency Discovery In Data Streams

With Marian Scuturici (Database Team, LIRIS), Céline Robardet (DM2L Team, LIRIS) and Antoine Fraboulet (HiKoB). This work was partially funded by the LIRIS Project Stream Mining.

TEDDY Algorithm

Pattern mining over data streams is critical to a variety of applications such as prediction and evolution of weather phenomena or anomaly detection in security applications. Most of the current techniques attempt to discover associations between events appearing on the same data stream but are not able to discover associations over multiple heterogeneous data streams. In this work, we aim to identify temporal dependencies between data streams. We represent event streams by state streams that are induced by the streams' events themselves. Each state has a duration, represented as a set of disjoint time intervals with respect to the events that occurred in the stream. Temporal relations between these interval sets infers dependencies between the corresponding datasources. Our interval-based approach is robust to the temporal variability of events that characterizes the time intervals during which the events are related. It links two types of events if the occurrence of one is often followed by the appearance of the other in a certain time interval. The proposed approach determines the most appropriate time intervals of a temporal dependency whose validity is assessed by a chi2 test. As several intervals may redundantly describe the same dependency, the approach retrieves only the few most specific intervals with respect to a dominance relationship over temporal dependencies, and thus avoids the classical problem of pattern flooding in data mining. TEDDY algorithm, TEmporal Dependency DiscoverY, prunes the search space while certifying the discovery of all valid and significant temporal dependencies. We present empirical results on simulated data to show the scalability and the robustness of our approach. We also report on case studies from smart real-world environments equipped with a number of cameras and motion sensors. These experiments demonstrate the efficiency and the effectiveness of our approach.

Applications

Triggering Road De-icing Operations

We present how these dependencies can be used within the GrizzLY project to tackle an environmental and technical issue: the deicing of the roads. This project aims to wisely organize the deicing operations of an urban area, based on several sensor network measures of local atmospheric phenomena. A spatial and temporal dependency-based model is built from these data to predict freezing alerts.

For more details:

  • Céline Robardet, Vasile-Marian Scuturici, Marc Plantevit, and Antoine Fraboulet. 2013. When TEDDY meets GrizzLY: temporal dependency discovery for triggering road deicing operations. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '13), Inderjit S. Dhillon, Yehuda Koren, Rayid Ghani, Ted E. Senator, Paul Bradley, Rajesh Parekh, Jingrui He, Robert L. Grossman, and Ramasamy Uthurusamy (Eds.). ACM, New York, NY, USA, 1490-1493. DOI=10.1145/2487575.2487706 http://doi.acm.org/10.1145/2487575.2487706

teddy.txt · Last modified: 2013/10/04 09:17 by mplantev
CC Attribution-Noncommercial-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0