Back to results
US 11,892,904 B2Granted
Directed incremental clustering of causally related events using multi-layered small world networks
AssigneeBMC Software, Inc.
InventorsSai Eswar Garapati, Erhan Giral
Life of this patent
Estimating the term…
Abstract
Described systems and techniques determine causal associations between events that occur within an information technology landscape. Individual situations that are likely to represent active occurrences requiring a response may be identified as causal event clusters, without requiring manual tuning to determine cluster boundaries. Consequently, it is possible to identify root causes, analyze effects, predict future events, and prevent undesired outcomes, even in complicated, dispersed, interconnected systems.
Claims20
A computer program product, the computer program product being tangibly embodied on a non-transitory computer-readable storage medium and comprising instructions that, when executed by at least one computing device, are configured to cause the at least one computing device to:
- determine a plurality of events within a network;
- determine, from the plurality of events, a plurality of causal event pairs within a multi-layer small world graph that includes a plurality of layers in which a lowest layer includes the plurality of events, an intervening layer includes an intervening subset of the plurality of events, and a highest layer includes a highest subset of the intervening subset, wherein the lowest layer includes lowest causal connections between causal event pairs of the plurality of events, the intervening layer includes intervening causal connections between causal event pairs of the intervening subset of events, and the highest layer includes a highest causal connection between a causal event pair of the highest subset, and further wherein the highest causal connection subsumes at least two of the intervening causal connections and each of the intervening causal connections subsumes at least two of the lowest causal connections;
- generate an arborescence graph from the plurality of causal event pairs within the multi-layer small world graph;
- generate a cluster tree of candidate event clusters from the arborescence graph;
- and
- select an event cluster from the candidate event clusters to thereby identify a situation within the network.
3 more elements
A computer-implemented method, the method comprising:
- determining a plurality of events within a network;
- determining, from the plurality of events, a plurality of causal event pairs within a multi-layer small world graph that includes a plurality of layers in which a lowest layer includes the plurality of events, an intervening layer includes an intervening subset of the plurality of events, and a highest layer includes a highest subset of the intervening subset, wherein the lowest layer includes lowest causal connections between causal event pairs of the plurality of events, the intervening layer includes intervening causal connections between causal event pairs of the intervening subset of events, and the highest layer includes a highest causal connection between a causal event pair of the highest subset, and further wherein the highest causal connection subsumes at least two of the intervening causal connections and each of the intervening causal connections subsumes at least two of the lowest causal connections;
- generating an arborescence graph from the plurality of causal event pairs within the multi-layer small world graph;
- generating a cluster tree of candidate event clusters from the arborescence graph;
- and
- selecting an event cluster from the candidate event clusters to thereby identify a situation within the network.
3 more elements
A system comprising:
- at least one memory including instructions;
- and
- at least one processor that is operably coupled to the at least one memory and that is arranged and configured to execute instructions that, when executed, cause the at least one processor to:
- determine a plurality of events within a network;
- determine, from the plurality of events, a plurality of causal event pairs within a multi-layer small world graph that includes a plurality of layers in which a lowest layer includes the plurality of events, an intervening layer includes an intervening subset of the plurality of events, and a highest layer includes a highest subset of the intervening subset, wherein the lowest layer includes lowest causal connections between causal event pairs of the plurality of events, the intervening layer includes intervening causal connections between causal event pairs of the intervening subset of events, and the highest layer includes a highest causal connection between a causal event pair of the highest subset, and further wherein the highest causal connection subsumes at least two of the intervening causal connections and each of the intervening causal connections subsumes at least two of the lowest causal connections;
- generate an arborescence graph from the plurality of causal event pairs within the multi-layer small world graph;
- generate a cluster tree of candidate event clusters from the arborescence graph;
- and
- select an event cluster from the candidate event clusters to thereby identify a situation within the network.
6 more elements
Dependencies are inferred from the claim text.