Searching for Structure in Multiple Streams of Data

Abstract

Finding structure in multiple streams of data is an important problem. Consider the streams of data flowing from a robot's sensors, the monitors in an intensive care unit, or periodic measurements of various indicators of the health of the economy. There is clearly utility in determining howcurrent and past values in those streams are related to future values. We formulate the problem of finding structure in multiple streams of categorical data as searchover the space of dependencies, unexpectedly frequentor infrequent co-occurrences, between complex patterns of values that can appear in the streams. Based on that formulation, we develop the Multi-Stream Dependency Detection (msdd) algorithm that performs an efficient systematic searchover the space of all possible dependencies. Dependency strength is evaluated with a statistical measure of nonindependence, and bounds that we derivefor the value of that measure allow the search to be pruned. Due to the pruning, can find the k strongest dependencies in the streams by examining only a fraction of the search space.