Affiliations: [a] Univ Lyon, Université Lyon, Villeurbanne, France | [b] Univ Lyon, INSA Lyon, CNRS, Villeurbanne, France
Correspondence:
[*]
Corresponding author: Marc Plantevit, Univ Lyon, Université Lyon 1, CNRS, LIRIS UMR5205, F-69622, Villeurbanne, France. E-mail:[email protected]
Abstract: Pattern mining over data streams is critical to a variety of
applications such as understanding and predicting weather phenomena
or outdoor surveillance. Most of the current techniques attempt to
discover relationships between time-point events but are not
practical for discovering dependencies over interval-based
events. In this work, we present a new approach to mine dependencies
between streams of interval-based events that links two events if
they occur in a similar manner, one being often followed by the
other one after a certain time interval in the data.
The proposed method is robust to temporal
variability of events and determines the most appropriate time
intervals whose validity is assessed by a χ^2 test. As several
intervals may redundantly describe the same dependency, the approach
retrieves only the most specific intervals with respect to a
dominance relationship over temporal dependencies, and thus avoids
the classical problem of pattern flooding in data mining. The TEDDY
algorithm, TEmporal Dependency DiscoverY, prunes the search space
while guaranteeing the discovery of all valid and significant temporal
dependencies. We present empirical results on simulated and real-life data to
show the scalability and the robustness of our approach. The
dependency relationships define a graph that supports intelligent
analysis as illustrated by two case studies: Outdoor
surveillance of a building via video camera and motion
sensors, and assistance for road deicing operations based on the
humidity and temperature measurements at the urban scale.
These applications demonstrate the efficiency and the
effectiveness of our approach.
Keywords: Temporal dependencies, data streams, sensor network analysis
