System and methods for display of time-series data distribution

• US 7,219,034 B2
• Filed: 09/13/2002
• Issued: 05/15/2007
• Est. Priority Date: 09/13/2001
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: OPNET Technologies Incorporated (Riverbed Technology Incorporated)
• Inventors: Courtemanche, Michael B., McGee, John J., Beck, Ralph L.
• Primary Examiner(s): Hoff; Marc S.
• Assistant Examiner(s): Desta; Elias
• Application Number:
  US10/243,534
• Publication Number:
  US 20030088542A1
• Time in Patent Office: 1,705 Days
• Field of Search: 702/179, 702/180, 702/182, 382/168, 382/171, 382/241, 348/672, 358/500, 358/522, 707/101, 707/6, 707/7
• US Class Current: 702/180
• CPC Class Codes: G06F 11/323 Visualisation of programs or trace data
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and methods for displaying data distribution information for time-series data is described. The methods include computing a condensed quantile function that may be used to generate approximate histograms for the time-series data, while decreasing the data storage requirements for generating a series of histograms for time-series data. The methods further include displaying the data distribution information using stack-bar histograms, many of which may be shown in a single display to permit a user to discern trends in the data distribution information. Methods for merging condensed quantile function tables are also described.

Claims

1. A method for optimizing a distributed process system including providing a visual indication of behavior and trends by generating an approximate histogram of a data set, the method comprising the steps of:

applying a quantile function on the data set to create a computational result;

selecting a subset of the data set in response to the computational result;

determining a condensed quantile function from the subset of the data set; and

rendering the approximate visual histogram display in response to the condensed quantile function, including

calculating an expected sample count based at least in part on an inverse of the condensed quantile function.

2. The method of claim 1 wherein the subset of the data set includes at least one of a minimum value of the data set, a median value of the data set, and a maximum value of the data set.

3. The method of claim 1 wherein the step of determining the condensed quantile function further comprises the step of interpolating between a plurality of values in the data set.

4. The method of claim 1 wherein the interpolating step comprises at least one of the linear interpolation and polynomial interpolation.

5. The method of claim 1 wherein the approximate histogram comprises a plurality of bins, the rendering step further comprising the steps of:

reducing the plurality of bins in the approximate histogram into a plurality of adjacent cells; and

applying an indicium to each cell in response to a percentage of the data set within each cell.

6. The method of claim 5 wherein the indicium is visually discernable.

7. The method of claim 1 for optimizing a distributed process system including providing a visual indication of behavior and trends, further comprising the steps of merging a plurality of data sets with reduced data storage requirements, comprising the steps of:

calculating a condensed quantile function for each data set, each condensed quantile function supplying quantile values;

interleaving the quantile values;

calculating an inverse of each condensed quantile function at each interleaved quantile value;

calculating an average of the inverse of the condensed quantile functions at each interleaved quantile value;

defining a merged quantile function as an inverse of the average of the inverse of the condensed quantile functions at each interleaved quantile value, and

rendering a merged histogram in response to the merged quantile function.

8. The method of claim 7 wherein the plurality of data sets comprise data associated with a single variable from adjacent time intervals.

9. The method of claim 7 wherein the plurality of data sets comprise data associated with a plurality of instances of a single variable from a single time interval.

10. The method of claim 7 wherein the step of rendering the merged histogram further comprises the step of calculating an expected sample count based at least in part on an inverse of the merged quantile function.

11. The method of claim 7 wherein the step of rendering the merged histogram further comprises the steps of:

reducing a plurality of bins in the merged histogram into a plurality of adjacent cells; and

applying an indicium to each cell in response to a percentage of the data set within each cell.

12. The method of claim 11 wherein the indicium is visually discernable.

13. A method of optimizing performance in a distributed transaction system, the method comprising the steps of:

collecting data associated with at least one system performance metric;

applying a quantile function on the data to create a computational result;

selecting a subset of the data in response to the computational result;

determining a condensed quantile function from the subset of the data;

rendering at least one approximate histogram in response to the condensed quantile function, including

calculating an expected sample count based at least in part on an inverse of the condensed quantile function;

identifying at least one trend in the at least one approximate histogram; and

adjusting, on an as needed basis, operation of the distributed transaction system to modify the at least one trend.

14. An apparatus for optimizing performance in a distributed transaction system comprising:

a data collection apparatus for collecting transaction system performance data;

logic to apply a quantile function to the transaction system performance data, creating a computational result;

logic to select a subset of the transaction system performance data in response to the computational result;

logic to determine a condensed quantile function from the subset of the transaction system performance data;

logic to render an approximate histogram in response to the condensed quantile function, including

calculating an expected sample count based at least in part on an inverse of the condensed quantile function; and

a display to render the approximate histogram.

15. An article of manufacture comprising a program storage medium having computer readable program code embodied therein for causing the generation of an approximate histogram of a data set, the computer readable program code in the article of manufacture including:

computer readable code for causing a computer to apply a quantile function on the data set to create a computational result;

computer readable code for causing a computer to select a subset of the data set in response to the computational result;

computer readable code for causing a computer to determine a condensed quantile function from the subset of the data set; and

computer readable code for causing a computer to render the approximate histogram in response to the condensed quantile function, so as to generate the approximate histogram, including

calculating an expected sample count based at least in part on an inverse of the condensed quantile function.

16. A program storage medium readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for generating an approximate histogram of a data set, the method steps comprising:

applying a quantile function on the data set to create a computational result;

selecting a subset of the data set in response to the computational result;

determining a condensed quantile function from the subset of the data set; and

rendering the approximate histogram in response to the condensed quantile function, so as to generate the approximate histogram, including

calculating an expected sample count based at least in part on an inverse of the condensed quantile function.

17. A method for detecting irregularities in time series data representing the performance of a complex system, comprising the steps of:

generating a quantile representation of at least one time series segment of the time series data,

determining a condensed quantile representation of the at least one segment,

merging sets of the condensed quantile representations,

rendering an approximate histogram of each merged set of the condensed quantile representations, and

concurrently displaying a plurality of associated histograms of merged sets of condensed quantile representations as a set of stack-bar histogram charts.