Systems and/or methods for statistical online analysis of large and potentially heterogeneous data sets

• US 9,122,786 B2
• Filed: 09/14/2012
• Issued: 09/01/2015
• Est. Priority Date: 09/14/2012
• Status: Active Grant

• Current Assignee: Software AG
• Original Assignee: Software AG
• Inventors: Cammert, Michael, Heinz, Christoph, Krmer, Jrgen, Riemenschneider, Tobias
• Primary Examiner(s): McDowell, Jr., Maurice L
• Assistant Examiner(s): Ricks, Donna J
• Application Number:
  US13/616,952
• Publication Number:
  US 20140078163A1
• Time in Patent Office: 1,082 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3471 Address tracing
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches

Abstract

Certain example embodiments relate to using Complex Event Processing (CEP) techniques for statistical analysis of cache behavior and parameters, e.g., in connection with large, potentially heterogeneous data sets (e.g., “Big Data”). A dedicated stream mining operator registers a listener to a cache and receives notifications on cache operations. For selected element attributes, a first model estimates the probability density functions of the attribute values, delivering well-defined estimates of the attribute value distributions. A second model analyzes the time elements stay in the cache (“validity”). Validity is combined with the attribute value distribution. A meaningful analysis model (Cache Element Model) can be derived by combining additional summary statistics for the validity with the attribute value distribution, describing how long elements stay in the cache for attribute values of a specific region, and how the values are distributed. It may be used to inform administrative tasks such as, optimization of cache parameters.

Claims

1. A method of analyzing the behavior and parameters of a cache in a computer system over a temporal range of analysis, the method comprising:

receiving, over a first stream, notifications indicating that respective cache operations have been performed in connection with respective elements and the cache, each said operation having an operation type, the operation type being designated as one of an insert, update, or remove operation for the respective element; and

for each received notification where a selected element attribute of interest is available therein;

extracting, from the respective notification, information regarding a key of the respective element, the respective selected element attribute of interest, the respective operation type, and respective timestamp(s) associated with the respective operation; and

computing value and validity distribution models using the extracted information;

wherein the computing of the value distribution model, in connection with a given notification and an associated given element, comprises;

updating a temporal buffer of inserted and not yet removed and/or updated elements to include an entry for the given element, the temporal buffer defining a range of elements to be considered in the computing of the value distribution model; and

calculating a value distribution for the selected attribute of interest based on elements in the temporal buffer; and

wherein the computing of the validity model, in connection with a given notification and an associated given element, comprises;

ignoring the given notification when the given element has an insert operation type;

calculating a validity value for the given element as a difference between first and second timestamps,

for remove operation types, the first timestamp indicating when the given element was removed and the second timestamp indicating when the given element was inserted, and

for update operation types, the first timestamp indicating when an old element was removed and the given element was inserted and the second timestamp indicating when the old element was inserted;

ignoring the given notification and the given element when the validity value is greater than a window size corresponding to the temporal range of analysis; and

when the validity value is less than or equal to the window size;

determining a temporal partition of the temporal range of analysis into which the attribute of interest associated with the given element falls; and

publishing an event to a second stream, the event indicating the validity value and the determined temporal partition; and

running a query on the second stream in order to derive summary statistics for validity values in the partitions.

2. The method of claim 1, further comprising generating a combined model based on the computed value and validity distribution models.

3. The method of claim 2, further comprising outputting a visual representation of at least the combined model to a display device.

4. The method of claim 3, wherein the visual representation includes summary validity statistics including minimum, maximum, average, and standard deviation of the validity length.

5. The method of claim 1, further comprising plotting the value distribution for the attribute of interest in a graph, the graph having colors and/or other indicators in order to also reflect an aspect of the validity distribution model therein.

6. The method of claim 1, further comprising:

receiving input designating the attribute of interest;

computing value and validity distributions for the designated attribute of interest;

plotting the value distribution for the attribute of interest in a graph in accordance with a first coordinate system;

partitioning a first axis of the first coordinate system in accordance with temporal partitions of the temporal range;

receiving input designating one statistical summary measure of validity;

for each partition of the first axis and summary measure, computing a color from a predefined color range using the relative ordering of the summary measures across the partitions; and

for each said partition, filling the area between first axis and value distribution with the corresponding color.

7. The method of claim 6, further comprising labeling each partition with associated summary measure value.

8. The method of claim 1, further comprising generating a graph including Box-and-Whisker plots of validity statistics for each said temporal partition.

9. The method of claim 1, wherein the temporal range is updatable by a user.

10. The method of claim 1, wherein the updating of the temporal buffer comprises:

for an insert operation, inserting the respective element into the buffer, and removing older elements from the buffer if necessary to fit temporal range constraints;

for a remove operation, removing the respective element from the buffer; and

for an update operation, removing the old element from the buffer followed by inserting the new element into the buffer.

11. The method of claim 1, wherein the calculating of the value distribution is performed in connection with a kernel function and bandwidth strategy.

12. The method of claim 1, wherein:

the calculating of the value distribution is performed in connection with kernel density estimation and predetermined kernel function and bandwidth parameters, and

the predetermined kernel function parameter specifies Epanechnikow kernel functionality and a Normal Scale Rule is used for computing the bandwidth.

13. The method of claim 12, wherein the Normal Scale Rule is updated each time an element enters or leaves the buffer, thereby reflecting a new bandwidth.

14. The method of claim 1, wherein the computer system includes multiple caches and the first stream receives notifications only for a preselected one or more caches of the computer system.

15. The method of claim 1, wherein each said notification includes at least a key of the associated element and one or more attributes of the associated element.

16. A non-transitory computer readable storage medium tangibly storing a computer program comprising instructions that, when executed, perform a method according to claim 1.

27. The system of claim 16, wherein:

the calculating of the value distribution is performed in connection with kernel density estimation and predetermined kernel function and bandwidth parameters,

the predetermined kernel function parameter specifies Epanechnikow kernel functionality and a Normal Scale Rule is used for computing the bandwidth, and

the Normal Scale Rule is updated each time an element enters or leaves the temporal buffer.

17. An event processing system for analyzing the behavior and parameters of a cache in a computer system over a temporal range of analysis, comprising:

an event bus configured to receive a first stream of events corresponding to respective operations on the cache, each said event being associated with a respective element operating on the cache, each said operation having an operation type, and the operation type being selected from the group consisting of insert, update, and remove operation types; and

an event processing engine comprising processing resources including at least one processor, the event processing engine being configured, for each event received from the first stream where the respective element has a pre-selected attribute of interest associated therewith, to;

(a) compute a value distribution model by at least;

updating a temporal buffer of inserted and not yet removed and/or updated elements to include an entry for the respective element, the temporal buffer defining a range of elements to be considered in computing the value distribution model and including at least data indicative of the attribute of interest for the elements therein, and

calculating a value distribution of the attributes of interest for the elements in the temporal buffer; and

(b) compute a validity distribution model by at least;

ignoring the respective event when the given element has an insert operation type;

calculating a validity value for the respective element as a difference between first and second timestamps,

the first timestamp indicating when the given element was removed and the second timestamp indicating when the given element was inserted for remove operation types, and

the first timestamp indicating when an old element was removed and the given element was inserted and the second timestamp indicating when the old element was inserted for update operation types;

ignoring the respective event when the validity value is greater than a window size corresponding to the temporal range of analysis; and

when the validity value is less than or equal to the window size;

determining a temporal partition of the temporal range of analysis into which the attribute of interest associated with the given element falls; and

publishing a new event to a second stream of events, the new event indicating the validity value and the determined temporal partition; and

running a query on the second stream in order to derive summary statistics for validity values in the partitions.

18. The system of claim 17, wherein the event processing engine is further configured to generate a combined model based on the computed value and validity distribution models.

19. The system of claim 17, wherein the event processing engine is further configured to generate output corresponding to a visual representation of at least the combined model for display on a display device of the system.

20. The system of claim 17, wherein the event processing engine is further configured to plot, in a user interface, the value distribution for the attribute of interest in a graph, the graph having colors and/or other indicators in order to also reflect an aspect of the validity distribution model therein.

21. The system of claim 17, further comprising a user interface configured to receive input designating the attribute of interest and input designating one statistical summary measure of validity,

wherein the event processing engine is further configured to:

plot the value distribution for the attribute of interest in a graph in accordance with an XY coordinate system;

partition the X axis of the XY coordinate system in accordance with predefined temporal partitions of the temporal range;

for each partition of the X axis and summary measure, compute a color from a predefined color range using the relative ordering of the summary measures across the partitions; and

for each said partition, fill the area between X axis and value distribution with the corresponding color.

22. The system of claim 21, wherein the event processing engine is further configured to label each partition with an associated summary measure value.

23. The system of claim 17, wherein the temporal range is updatable by a user.

24. The system of claim 17, wherein the updating of the temporal buffer comprises:

for an insert operation, inserting the respective element into the buffer, and removing older elements from the buffer if necessary to fit temporal range constraints;

for a remove operation, removing the respective element from the buffer; and

for an update operation, removing the old element from the buffer followed by inserting the new element into the buffer.

25. The system of claim 17, wherein the computer system includes multiple caches and the first stream receives events only for a preselected one or more caches of the computer system.

26. The system of claim 17, wherein the calculating of the value distribution is performed in connection with a kernel function and a bandwidth strategy.