Method and apparatus for digital data compression

• US 5,748,781 A
• Filed: 01/04/1995
• Issued: 05/05/1998
• Est. Priority Date: 01/04/1995
• Status: Expired due to Term

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Carlson, David G., Datta, Utpal
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/368,414
• Time in Patent Office: 1,217 Days
• Field of Search: 382/232, 382/197, 382/235, 382/202, 382/203, 382/201, 345/121
• US Class Current: 382/232
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding

Abstract

Data compression and decompression are performed on a series of data points, by expressing a plurality of data points as an equation or a series of equations. Variable accuracies, and accordingly variable compression ratios, may be provided. Multiple versions of the compressed data, with corresponding multiple accuracy levels, and resulting multiple decompressions may be displayed for comparison. The method and apparatus may be used for storing network statistical data.

Claims

1. A method for compressing a series of data points, the method comprising the steps of:

(A) determining a first equation which represents a first plurality of data points from the series and storing the first equation as a first compressed node, the slope of the first equation being an average of a plurality of slopes, each of the plurality of slopes being a slope between two adjacent data points of the first plurality of data points;

(B) determining an allowable range for a next data point in the series of data points based upon the first equation; and

(C) when a next data point is outside the allowable range, determining a second equation which represents a second plurality of data points and storing the second equation as a second compressed node.

2. The method of claim 1, further comprising the step of reproducing the data points.

3. The method of claim 2, further comprising the steps of:

monitoring a network for statistical data; and

providing the statistical data as the plurality of data points.

4. The method of claim 1, wherein step A includes:

storing a first data point of the first plurality of points, the first equation, and a number of data points in the first plurality of data points; and

step C includes

storing a first data point of the second plurality of data points, the second equation, and a number of data points in the second plurality of data points.

5. The method of claim 1, wherein the first equation and the second equation are linear equations.

6. The method of claim 5, wherein step A and C respectively include the steps of:

receiving an accuracy level;

determining a current slope for a current data point and a previous adjacent data point for each adjacent set of data points in the respective node;

determining a current average slope to be a rolling average of the previous current slopes;

determining the allowable range to be from R₁ to R₂ where;

R₁ =(the current data point)+(the current average slope)+((the current average slope)×

(100-accuracy level)/100));

R₂ =(the current data point)+(the current average slope)-((the current average slope)×

(100-accuracy level) /100)).

7. The method of claim 6, wherein the step of storing includes the steps of:

storing the first data point of the respective node;

storing the current average slope of the respective node; and

storing the number of data points in the respective node.

8. The method of claim 7, further including steps for reproducing data, the reproduced data including a plurality of reproduced data points, the method further comprising the steps of:

a. initializing a counter to zero;

b. determining a reproduced data point to be a sum of the first data point and a product of the counter multiplied by the current average slope of the respective node;

c. incrementing the counter by one; and

d. iterating step b and step c until the counter is equal to the number of data points in the respective node.

9. The method of claim 1, wherein:

step A includes determining a slope of the first equation; and

step B includes determining the allowable range based upon the slope of the first equation and an accuracy level.

10. The method of claim 9, wherein step B includes the steps of:

extrapolating the first equation to determine a projected next data point value;

determining an allowable margin based upon the slope of the first equation and the accuracy level; and

determining the allowable range to be a range from the projected next data point plus the allowable margin to the next projected data point minus the allowable margin.

11. A method for reproducing a series of original data points from compressed data, the method comprising the steps of:

a. receiving the compressed data, the compressed data including a first data point, a slope of an equation which represents a series of original data points, and the number of data points represented by the equation;

b. initializing a counter to zero;

c. determining a reproduced data point to be a sum of the first data point and a product of the counter multiplied by the slope;

d. incrementing the counter by one; and

e. iterating step c and step d until the counter is equal to the number of data points represented by the equation.

12. A method for compressing data with a plurality of accuracies, comprising the steps of:

receiving original data;

storing the original data in a first compressed format having a first accuracy level;

storing the original data in a second compressed format having a second accuracy level;

reproducing the original data from the first compressed format, to create a first reproduced data set;

reproducing the original data from the second compressed format, to create a second reproduced data set; and

displaying the first reproduced data set and the second reproduced data set concurrently.

13. The method of claim 12, wherein the first compressed format includes a first slope of a first equation, a first data point, a first number of data points defined by the first compressed format, and a first accuracy, and wherein the second compressed format includes a second slope of a second equation, a second data point, a second number of data points defined by the second compressed format, and a second accuracy, wherein the second accuracy is different from the first accuracy.

14. An apparatus for compressing a series of data points, the apparatus comprising:

first means for determining a first equation which represents a first plurality of data points from the series and for storing the first equation as a first compressed node, the slope of the first equation being an average of a plurality of slopes each of the plurality of slopes being a slope between two adjacent data points of the first plurality of data points;

second means for determining an allowable range for a next data point in the series of data points based upon the first equation; and

third means, coupled to the first and second means, for determining a second equation that represents a second plurality of data points and for storing the second equation as a second compressed node when a next data point is outside the allowable range.

15. The apparatus of claim 14, further comprising means, coupled to the first and third means for determining, for reproducing the data points.

16. The apparatus of claim 14, further comprising means, coupled to the first and third means for determining, for monitoring a network for statistical data and for providing the statistical data to the first and third means for determining.

17. The apparatus of claim 14, wherein:

the first means includes means for determining a slope of the first equation; and

the second means includes means for determining the allowable range based upon the slope of the first equation and an accuracy level.

18. The apparatus of claim 17, wherein the second means includes:

means for extrapolating the first equation to determine a projected next data point value;

means for determining an allowable margin based upon the slope of the first equation and the accuracy level; and

means for determining the allowable range to be a range from the projected next data point plus the allowable margin to the next projected data point minus the allowable margin.

19. An apparatus for reproducing a series of original data points from compressed data, the apparatus comprising:

means for receiving the compressed data, the compressed data including a first data point, a slope of an equation which represents a plurality of original data points from the series, and the number of data points represented by the equation;

means, coupled to the means for receiving, for initializing a counter to zero; and

reproducing means, coupled to the means for receiving and the means for initializing, for determining a reproduced data point to be a sum of the first data point and a product of the counter multiplied by the slope, and for incrementing the counter by one when the counter is less than the number.

20. An apparatus for compressing data with a plurality of accuracies, comprising:

means for receiving original data;

means, coupled to the means for receiving, for storing the original data in a first compressed format with a first accuracy level;

means, coupled to the means for receiving, for storing the original data in a second compressed format having a second accuracy level;

means, coupled to the first means for storing, for reproducing the original data from the first compressed format, to create a first reproduced data set;

means, coupled to the second means for storing, for reproducing the original data from the second compressed format, to create a second reproduced data set; and

means, coupled to the first and second means for reproducing, for displaying the first reproduced data set and the second reproduced data set concurrently.

21. A memory device containing a computer program of instructions for a general purpose computer to compress data, the data comprising a series of data points, the memory device comprising:

first means for providing instructions for determining a first equation which represents a first plurality of data points from the series of data points, and for storing the first equation as a first compressed node, the slope of the first equation being an average of a plurality of slopes, each of the plurality of slopes being a slope between two adjacent data points of the first plurality of data points;

second means for providing instructions for determining an allowable range for a next data point in the series of data points based upon the first equation; and

third means, coupled to the first and second means, for providing instructions for determining a second equation that represents a second plurality of data points and for storing the second equation as a second compressed node when a next data point is outside the allowable range.

22. The memory device of claim 21, further comprising means, coupled to the first and third means, for providing instructions for reproducing the data points.

23. The memory device of claim 21, further comprising means, coupled to the first and third means, for providing instructions for monitoring a network for statistical data and for providing the statistical data to the first and third means for providing instructions for determining.

24. The memory device of claim 21, wherein:

the first means includes means for determining a slope of the first equation; and

the second means includes means for determining the allowable range based upon the slope of the first equation and an accuracy level.

25. The memory device of claim 24, wherein the second means includes:

means for extrapolating the first equation to determine a projected next data point value;

means for determining an allowable margin based upon the slope of the first equation and the accuracy level; and

means for determining the allowable range to be a range from the projected next data point plus the allowable margin to the next projected data point minus the allowable margin.

26. A memory device containing a computer program of instructions for a general purpose computer to reproduce a series of original data points from compressed data, the memory device comprising:

a first means for providing instructions for receiving the compressed data, the compressed data including a first data point, a slope of an equation which represents a plurality of original data points from the series, and the number of data points represented by the equation;

a second means, coupled to the first means, for providing instructions for initializing a counter to zero;

a third means, coupled to the first and second means, for providing instructions for determining a reproduced data point to be a sum of the first data point and a product of the counter multiplied by the slope, when the counter is less than the number of data points represented by the equation.

27. A memory device containing a computer program of instructions for a general purpose computer to compress data with a plurality of accuracies, the memory device comprising:

first means for providing instructions for receiving original data;

second means, coupled to the first means, for providing instructions for storing the original data in a first compressed format having a first accuracy level;

third means, coupled to the first means, for providing instructions for storing the original data in a second compressed format having a second accuracy level;

fourth means, coupled to the second means, for providing instructions for reproducing the original data from the first compressed format, to create a first reproduced data set;

fifth means, coupled to the third means, for providing instructions for reproducing the original data from the second compressed format, to create a second reproduced data set; and

sixth means, coupled to the fourth and fifth means, for providing instructions for displaying the first reproduced data set and the second reproduced data set concurrently.