Database Reference
In-Depth Information
different nodes of a distributed system. Each such trace represents a
linear event sequence that logs the execution order of events on a single
processor in the system. The tool first finds all communication events
and matches each sending event to the corresponding receiving event
(for each message). The resulting arcs, together with the original event
sequences give rise to event graphs, which are then mined for discrimina-
tive patterns. The discriminative graph mining algorithm first identifies
individual discriminative events, then grows these events recursively into
bigger patterns using a set of rules that aim to maximize the information
gain (i.e., discriminative ability) of the resulting pattern at each step.
A search tree is created whose root is a single discriminative event, and
where every node is a discriminative event subgraph. A node's childern
represent all ways the (discriminative) event subgraph at the parent node
can be extended by one event. Additional rules specify how to grow a
pattern to make sure that the space of patterns reached from different
search tree branches is not overlapping. For example, a pattern where
event
a
is followed by
b
should not be a child of both of the aforemen-
tioned individual events. Rather, growth should occur in a specified
direction only to eliminate any possible redundancy between different
search tree branches.
The tool was used to debug a sensor data aggregation and regression
modeling framework that collected measurements from on-board diag-
nostic interface ports (OBD-II ports) of different vehicles while testing
a new navigation service [29]. It was found that, depending on which
vehicles were involved in the data collection, some resulting computed
models of the data were very poor. Using PopMine, the found bug
was attributed to a condition where measurements were collected from
two vehicles reporting data in conflicting units. Note that, reporting in
either unit consistently would have worked (generating results in that
unit), but aggregating conflicting units resulted in an error. The bug
triggering condition, in this case, was a graph in which two modules
(the two cars with conflicting unit settings) fed a single aggregator. By
inspecting the data feeds from the identified cars manually, the issue of
conflicting units was recognized.
3.3 Symbolic Pattern Mining
The above “unit mismatch” example, upon closer examination, trig-
gers the observation that discriminative subgraph mining and its prede-
cessors (e.g., discriminative event mining, itemset mining, and sequence
mining) suffer from the same ineciency: namely, they are unable to
generalize from individual examples to categories that satisfy a particu-
