Computer storage capacity forecasting system using cluster-based seasonality analysis

• US 7,783,510 B1
• Filed: 06/25/2007
• Issued: 08/24/2010
• Est. Priority Date: 06/23/2006
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: Perka, Michael F., Gilgur, Alexander
• Primary Examiner(s): DIXON, THOMAS A
• Application Number:
  US11/823,108
• Time in Patent Office: 1,156 Days
• Field of Search: 705/7, 705/10
• US Class Current: 705/7.25
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities

Abstract

A methodology for automatic a priori data pattern analysis is provided. Described methods allow consistent and objective determination of outliers; trend; seasonality; and level shifts; and the production of better models and more accurate forecasts. In addition, a two-step way to automatically determine seasonality and locate possible events in the data set is described. Decomposition of data into seasonal, trend and level components; detection of outliers and level-shift events in the time series based on statistical analysis of the time series; detection of seasonality based on statistical analysis of clusters of data, known as cluster-based seasonality analysis, or CBSA; evaluation of the goodness of fit of a model to data, using the existing goodness of fit indicator, R²; and seasonality analysis, using a sequence of cluster-based seasonality analysis (CBSA) and Fourier analysis are described.

Claims

1. A system for generating a forecasting model for storage capacity planning, the system comprising:

a computer system comprising computer hardware, the computer system programmed to implement;

a data pattern analysis engine configured to;

receive time series data reflecting computer storage capacity;

identify a trend in the received time series data, using the received data, said identifying the trend comprising performing a transform of the time series data to derive a parameter, using the parameter to calculate a goodness-of-fit for a selected trend, and selecting the trend based at least partly on the calculated goodness-of-fit;

perform cluster-based seasonality analysis to identify seasonality in the received time series data, said performing comprising analyzing intervals between consecutive events to detect the seasonality; and

a forecast engine configured to select a forecast model adapted to predict an amount of additional computer storage capacity to obtain in the future and when to obtain the additional computer storage capacity, the forecast model operative to select the forecast model based at least partly on the identified trend and seasonality.

2. The system of claim 1, wherein the data pattern analysis engine is further configured to perform the cluster-based seasonality analysis by at least grouping data points in said intervals into clusters.

3. The system of claim 2, wherein the data pattern analysis engine is further configured to perform the cluster-based seasonality analysis by at least determining sizes of the clusters and determining whether a distribution of the cluster sizes approximately corresponds to a Poisson probability distribution.

4. The system of claim 3, wherein the data pattern analysis engine is further configured to, in response to determining that the distribution does not approximately correspond to the Poisson probability distribution, perform Fourier analysis to identify the seasonality in the time series data.

5. The system of claim 3, wherein the data pattern analysis engine is further configured to perform a Chi-square test to analyze the distribution'"'"'s goodness of fit with the Poisson probability distribution.

6. The system of claim 1, wherein identifying the outlier points comprises calculating a standard deviation and running mean of the time series data, determining whether any data point is within a number of standard deviations from the running mean, and considering each data point that is greater than the number of standard deviations of the running mean to be an outlier point.

7. A method for detecting seasonality in time series data, the method comprising:

by a computer system comprising computer hardware;

receiving time series data reflecting computer storage capacity;

identifying a plurality of events in the time series data, the events comprising one or more of outlier points and level shifts;

performing an interpolation of the outlier points by at least substituting a value of each outlier point with a value calculated using linear interpolation;

identifying a trend in the received time series data;

performing cluster-based seasonality analysis to identify a first seasonality in the received time series data, said performing comprising analyzing intervals between consecutive events to detect clusters of data points and analyzing the clusters to identify the first seasonality; and

generating a forecast model based at least in part on the identified trend and first seasonality, the forecast model adapted to predict an amount of additional computer storage capacity to obtain in the future and when to obtain the additional computer storage capacity.

8. The method of claim 7, further comprising performing Fourier analysis to identify a second seasonality.

9. The method of claim 8, using one of the first and second seasonalities to select a forecast model.

10. The method of claim 8, using both the first and second seasonalities to select a forecast model.

11. The method of claim 7, wherein identifying the outlier points comprises:

calculating a standard deviation and running mean of the time series data,

performing a T-test to determine whether any data point is within a number of standard deviations from the running mean, and

considering each data point that is greater than the number of standard deviations of the running mean to be an outlier point.

12. The method of claim 7, wherein said identifying the trend comprises:

performing a Fisher transform of the time series data to derive a parameter,

using the parameter to calculate a goodness-of-fit for a selected trend, and

selecting the trend based at least partly on the calculated goodness-of-fit.

13. A method for data forecasting, the method comprising:

by a computer system comprising computer hardware;

receiving time series data reflecting computer storage capacity; and

generating a forecasting model from the time series data, the forecasting model adapted to predict an amount of additional computer storage capacity to obtain in the future and when to obtain the additional computer storage capacity, said generating the forecasting model comprising;

identifying a plurality of events in the time series data, the events comprising outlier points, wherein identifying the outlier points comprises calculating a standard deviation and running mean of the time series data, determining whether any data point is within a number of standard deviations from the running mean, and considering each data point that is greater than the number of standard deviations of the running mean to be an outlier point;

performing an interpolation of the set of outlier points by at least substituting a value of each outlier point with a value calculated using linear interpolation;

identifying a trend in the received time series data, using the received data and the interpolation, said identifying the trend comprising performing a transform of the time series data to derive a parameter, using the parameter to calculate a goodness-of-fit for a selected trend, and selecting the trend based at least partly on the calculated goodness-of-fit;

performing cluster-based seasonality analysis to identify seasonality in the received time series data, said performing comprising analyzing intervals between consecutive events to detect the seasonality; and

creating the forecasting model based at least in part on the identified trend and seasonality.

14. The method of claim 13, wherein the events further comprise level shifts.

15. The method of claim 14, wherein said identifying the events further comprises detecting the level shifts from rate-of-change information derived from the time series data.

16. The method of claim 13, wherein said performing the cluster-based seasonality analysis further comprises grouping data points in said intervals into clusters.

17. The method of claim 16, wherein said performing the cluster-based seasonality analysis further comprises determining sizes of the clusters and determining whether a distribution of the cluster sizes approximately corresponds to a Poisson probability distribution.

18. The method of claim 16, further comprising, in response to determining that the distribution does not approximately correspond to the Poisson probability distribution, performing Fourier analysis to identify the seasonality in the time series data.

19. The method of claim 17, further comprising performing a Chi-square test to analyze the distribution'"'"'s goodness of fit with the Poisson probability distribution.

20. The method of claim 18, further comprising de-trending the time series data prior to performing the Fourier analysis.