Method and Apparatus for Digital Data Compression

This invention relates generally to data processing and more particularly to digital data compression and reproduction. It is particularly useful for the collection of network statistical data.

Existing methods of network statistical data collection normally poll the managed devices (i.e., network or end system nodes) for statistics and store them in a database/archive as statistical records. When the amount of data to be stored or communicated increases, the amount of processing, memory and communications resources required also increases. It would be desirable to decrease the amount of resources necessary to store and communicate data. Currently however, none of the network management products are known to store statistical data in a compressed form and reproduce them on demand.

Without data compression, for an exemplary set of 1000 data points the data content of each point is stored, resulting in storage of 1000 data points. The individual storage of these data points requires a certain amount of memory. If the data points were compressed and then stored, less memory would be required. The ratio of the amount of memory required if no compression is performed, to the amount of memory required if compression is performed, is known as the "compression ratio".

Several methods currently exist for compressing data. The data is usually divided into a string of symbols such as binary words, bytes, or ASCII characters, and the resulting string of symbols is divided into substrings of symbols. In general, the division of the input data stream into substrings is performed so that each substring is the longest string for which there is an identical substring in the input data stream. Short codes may then be developed which represent the substrings. In order that compressed data may be decompressed or reproduced, a dictionary is built as the substrings are replaced, linking each substring with the code that replaces it.

A first type of data compression method builds the dictionary from substrings for which matches have been found, for example substrings which occur more than once in the input data stream. The codes refer to locations in this dictionary, so that the substrings may be reproduced from the dictionary. Often, the dictionary of substrings is stored following the codes and the unmatched substrings.

The codes often comprise an ordered pair of values representing an offset and a length. The offset indicates the number of symbols between the substring (replaced by the code) and the location of the first symbol of the substring in the dictionary. The length indicates the number of symbols in the substring. The codes may also be referred to as pointers or indexes.

A second type of data compression method uses an existing dictionary, instead of building a new dictionary. This existing dictionary may be fixed, or it may have been built in a previous data compression of the first type. If it was built in a previous data compression, a buffer memory is reserved for retaining some portion of the previously compressed data which will be used as the dictionary. As in the first type, substrings are replaced by codes which reference the location of the replaced substring in the dictionary.

Accordingly, the first type and second type of methods only require storage space for one occurrence of a substring which may occur several times in an input data stream. However, a disadvantage of these methods is that the data compression ratio is often only in the range of 2 to 4.

Furthermore, these methods do not allow variable or multiple accuracy levels. Multiple accuracy levels enable higher data compression ratios where an accuracy below 100% is acceptable.

It is an object of the present invention to achieve a high compression ratio for the compression of digital data, such as network statistical data.

It is a further object to allow an externally-specified accuracy level for the reproduction of compressed data, to enable higher compression ratios when lower accuracy levels are sufficient.

It is a further object to allow an external device or user to evaluate the relative performance of different accuracy levels applied to the same data.

In order to achieve one or more of the foregoing objectives, the present invention includes a method and apparatus for compressing data by expressing a series of data points as an equation or a series of equations. Each equation describes a segment of the data series, which is then stored as a compressed node. A new equation may be initiated whenever a data point falls outside an allowable range for the next predicted point (according to the previous equation). In one embodiment, the equations are linear equations, with a "current slope" determined to be the slope between two adjacent data points in the data series, and a "current average slope" as a rolling average of all previous current slopes of an equation. The allowable range is determined from a desired accuracy level and the current average slope.

The invention further includes a method and apparatus for reproducing data. Reproduced data points are determined to be a sum of the first data point and a product of a counter multiplied by the current average slope. The counter is incremented to reproduce additional data points.

Furthermore, the invention enables variable accuracy which facilitates very high compression ratios in some instances. Additionally, it allows externally-specified accuracies.

In one embodiment, multiple accuracy levels are enabled, and raw data is compressed and stored. The data is then reproduced at different accuracy levels, and a display is provided for comparing the results of different accuracy levels.

Another embodiment provides a method and apparatus for monitoring a network, and compressing and storing network statistical data.

Further embodiments include a computer that performs the functions of several embodiments, as well as a memory device for providing instructions to a computer, so that the computer can perform the functions of the several embodiments.

These and other objects of the present invention will be more particularly described in the following drawings and detailed description.

FIG. 1 shows two process flows, one relating to a conventional method of data storage, and one for data storage according to the invention.

FIG. 2 is a flow chart illustrating generally a method of the present invention for storing compressed data.

FIG. 3 is a more detailed flow chart of the data storage mechanism.

FIG. 4 depicts a process flow diagram of the invention.

FIG. 5 depicts a graphical representation of the data compression, according to the invention.

FIG. 6 is a flow chart illustrating the reproduction or decompression of the compressed data, according to the invention.

FIG. 7 is a flow chart showing another embodiment in which multiple sets of compressed data are stored and displayed.

FIG. 8 shows another embodiment in which data compression is performed on network statistical data.

FIG. 9 shows a general purpose computer and memory, for alternative apparatus embodiments.

FIGS. 10(a), 10(b), and 10(c) show data in an uncompressed format.

FIG. 11 shows compressed data according to this invention, which corresponds to the data shown in FIGS. 10(a-c).

FIG. 12 shows one particular embodiment of the invention.

FIG. 13 shows another particular embodiment of the invention.

FIG. 14 shows yet another particular embodiment of the invention.

According to the method of this invention, a series of data consisting of data points is received and divided into segments which are represented by equations. Each segment is then stored as a node, instead of storing each data point individually.

FIG. 1 illustrates the data compression process of this invention, compared to a prior art process. A data series or stream 80 of 1000 data points includes three segments: a first segment 81, a second segment 82, and a third segment 83. These segments are defined by adjacent data points being within an allowable range of a current average slope for a segment as discussed further below. Data storage with no compression 84 (according to the prior art) results in the storage of 1000 individual data points 85, while data storage with compression 86 (the present invention) results in the storage of only 3 compressed nodes 87, corresponding to the three segments 81, 82, and 83.

FIG. 2 illustrates a flow chart for an embodiment of the invention. Step 11 defines the accuracy level to which the data will be compressed, which in turn defines an allowable range. In step 12, the data series is received, preferably one data point at a time. For each data point, step 13 determines whether the data point is within the allowable range. If the data point is within the allowable range, then the data is stored as part of a current segment (node) as depicted by step 14. If step 13 determines that a data point is not within the allowable range, then a new compressed node is initiated as shown in step 15. Thus, each compressed node corresponds to a segment of the data series, such as the segments 81, 82, and 83 as shown in FIG. 1.

FIG. 3 shows more detail of the data storage mechanism. Step 20 inputs the next data point. If step 21 determines that the next data point is the first of the node, then step 20 inputs another data point. If step 22 determines that the next data point is the second of the node, then step 23 calculates the slope between the first and second data points. This slope is called the "current slope". Additionally, a value called the "current average slope" is also initialized to be the slope between the first and second data points. For the next data point (i.e., not the first or second of the node), step 24 calculates the allowable margin for the next data point, by extrapolating the current average slope to a next predicted point, and defining the allowable margin to be the multiplication product of the current average slope and 100 minus the accuracy level, divided by 100.

The allowable range is then the range from the next predicted point minus the allowable margin, to the next predicted point plus the allowable margin. In other words, the difference between the accuracy level and 100 is the percentage of the current average slope that is equal to the allowable margin. The accuracy level may be input by a user or external device, or alternatively a default accuracy may be used. Normally, the accuracy level will be set to a value between 0 and 100, where an accuracy level of 100 means that the data is reproduced exactly.

Step 25 evaluates whether the next data point is within the allowable range determined in step 24. If the data point is within the allowable range, then step 26 recalculates the current average slope based on the next data point and the previous current average slope. For successive data points, the current average slope is determined to be a rolling average of the slopes between each adjacent pair of data points. For example, the current average slope after two data points are received is the slope between the two data points. When a third data point is received, the slope between the second and third data points is determined, and the current average slope is then determined to be the average of: the slope between the first and second data points, and the slope between the second and third data points.

Step 27 increments the number of data points for the current compressed node, and step 20 receives the next data point. In the event that the next data point is not within the allowable range as determined within step 24, then step 28 ends and defines the current compressed node. Each compressed node is defined by three elements: the starting point (the first data point within the compressed node); the current average slope; and the number of data points within the compressed node. Following step 28, step 29 begins a new compressed node which begins with the current data point. A next data point may then be received as in step 20.

FIG. 4 is a simplified process flow diagram which summarizes the present embodiment of data compression. Step 71 receives the input data stream. Step 72 calculates the slope, so that step 73 can determine whether the next data point is within the allowable range. If the next data point is within the allowable range, then step 74 determines a new average slope from the current slope and the previous current slopes, and the number of data points within the segment is incremented. Alternatively, if step 73 determines that the next data point is not within the allowable range, the compressed node is finished and stored as a starting point, an average slope, and a number of data points stored by the compressed node 75.

A graphical example of the data compression is depicted in FIG. 5. The x-axis 110 represents the data point being received, while the y-axis 111 represents the value of each data point. In this example, the first data point 112 has a value of 5. The second data point 113 has a value of 7. Thus, the first current slope 117 between these two adjacent points is (5-7)/1=2. Therefore, the current average slope is initialized to 2. The next predicted point 114 would be the extrapolation of the current average slope, which would be at the value of 9. If an accuracy level of 100 were specified, then the segment would continue only if the next data point were exactly 9, since any other value would fall outside of the allowable range. However, if an accuracy level such as 25 had been specified, then the allowable range 115 for the third data point would be from:

to:

based on a current average slope of 2.

Since in this example, the third data point 116 has a value of 8, it falls within the allowable range. The second current slope 118 is (8-7)/1=1, and the current average slope is now determined to be (2+1)/2=1.5. This new value of the current average slope then determines the allowable range for the fourth data point.

FIG. 6 depicts reproduction of the compressed data. For each compressed node, step 31 reads the value of the starting data point, the value of the current average slope, and the number of data points in the node. Step 32 reproduces each data point, by multiplying the slope by "i" and adding the resulting product to the first data point, where i is a monotonically increasing whole number which represents the relative placement of the specific data point within the node which is being reproduced. The value for i is initialized to zero for the first data point. Step 33 increments i, and step 34 determines whether i is equal to the number of data points in the node. If not, step 32 continues the decompression. If i is equal to the number of data points in the node, then the decompression of the node is complete, and step 35 continues to the next node to be decompressed.

Pseudo code for an embodiment of the compression method is as follows (where the current data point is identified as the "in data point"):

A pseudo code description of the reproduction process is as follows:

In summary, the present method embodiment utilizes linear equations for reducing a series of data points into corresponding compressed data nodes. Each data node is expressed as an equation of the form y=mx+b, where m is the slope and b is the first data point in the data node. Also stored is the number of data points. Each data point is represented by the value of y in the equation, where x is equal to 0 for the first data point, 1 for the second data point, 2 for the third data point, etc. In a reproduction process, x is equal to i, and i is incremented for each reproduced data point.

In other embodiments, non-linear equations may be implemented and/or the data may be compressed as several different types of equations. Any equation of the form y=f(x) may be implemented. Examples of such equations are: y=sin(x); y=cos(x); y=C.sub.(n) x.sup.(n) +C.sub.(n-1) x.sup.(n-1) . . . +C.sub.1 x+C.sub.0 ; y=1n(x); y=e.sup.x ; etc. In non-linear equations, the allowable range would normally be related to a parameter of the equation other than a slope. For example, the allowable range may be a percentage of the current data point.

The number of data points compressed into any one node depends upon the regularity of data values, and can vary from at least two to an indefinite number of data points. Each node contains enough information so that all of the original data points contained in the compressed node can be reproduced, within a specified range of accuracy. Multiple accuracy values can be specified at the beginning of the compression process, and several sets of compressed nodes may be generated, each corresponding to a different accuracy level. The default accuracy may be 100%, so that in the absence of specified accuracy levels, each of the reproduced data values will match the corresponding original data value exactly.

A further embodiment is illustrated in FIG. 7. Here, instead of storing the data with only a single accuracy level, multiple versions of the data are stored with different accuracy levels. In step 41, the default accuracy is set to 100%, although it is not necessary to have a default. Step 42 determines whether additional accuracy levels are required. If they are required, step 43 defines them. The data is then stored in step 44 in accordance with each required accuracy level. In step 45, the data is reproduced for each required accuracy level. Step 46 creates a graphical display which contains plots of data reproduced for each required accuracy level. Display 47 shows two such sets of data, one exemplary set of data 48 at a 90% accuracy, and another set of data 49 at a 80% accuracy. In this manner, a user or external device may evaluate the alternative accuracy levels.

FIG. 8 shows an embodiment of the invention in which data compression is performed on network statistical data. A collector of raw statistical data 52 (e.g., network management software running on a workstation) is connected to a live network 51. The collector 52 passes the data to a compressor 53, which compresses the data described above. The compressor 53 stores the data in a storage element 54, and a decompressor 55 decompresses the data, and makes it available to a requestor of statistical data 56 (i.e. a user or the network management software).

FIG. 12 shows an embodiment of the invention, including an apparatus for compressing a series of data points 124, the apparatus comprising a first equation generator 121 that determines a first equation which represents a first plurality of data points from the series 124 and that stores 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. The embodiment shown in FIG. 12 also includes an allowable range determinator 122 that determines an allowable range for a next data point in the series of data points based upon the first equation, and subsequent equation generator(s) 123, coupled to the first equation generator 121 and the allowable range determinator 122, that determines a second equation that represents a second plurality of data points and that stores the second equation as a subsequent compressed node 127 when a next data point is outside the allowable range.

Also shown in FIG. 12 is a network monitor 120, coupled to the first equation generator 121 and the subsequent equation generator 123, that monitors a network for statistical data 125 and that provides the statistical data 125 to the first equation generator 121 and the subsequent equation generator 123.

FIG. 13 shows another embodiment of the invention, including an apparatus for reproducing a series of original data points from compressed data 134, the apparatus comprising a data receiver 130 that receives the compressed data 134, 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. Also shown in FIG. 13 is a counter 132 and a counter initializer, coupled to the data receiver 130, for initializing the counter 132 to zero. Additionally, FIG. 13 shows a data reproducer 133, coupled to the data receiver 130 and the counter initializer 131, that determines a reproduced data point 135 to be a sum of the first data point an a product of the counter multiplied by the slope, and that incrementa the counter 132 by one when the counter is less than the number.

FIG. 14 shows another embodiment of the invention, directed to an apparatus for compressing data with a plurality of accuracies, comprising a data receiver 140 that receives original data 146, a first accuracy level storage 141, coupled to the data receiver 140, that stores the original data in a first compressed format with a first accuracy level, and a second accuracy level storage 142, also coupled to the data receiver 140, that stores the original data in a second compressed format with a second accuracy level. FIG. 14 also shows a first accuracy level data reproducer 143, coupled to the first accuracy level storage 141, that reproduces the original data from the first compressed format, to create a first reproduced data set 147, and a second accuracy level data reproducer 144, coupled to the second accuracy level storage 142, that reproduces the original data from the second compressed format, to create a second reproduced data set 148. FIG. 14 also shows a concurrent display 145, coupled to the first accuracy level data reproducer 143 and the second accuracy level data reproducer 144, that displays the first reproduced data set and the second reproduced data set concurrently.

Any of the above embodiments may be implemented in a general purpose computer 60 as shown in FIG. 9. This general purpose computer may include a Computer Processing Unit (CPU) 61, memory 62, a processing bus 63 by which the CPU can access the memory 62, and access to a network 64.

In alternative embodiments, the invention may be a computer apparatus which performs the functions of any of the previous embodiments. Alternatively, the invention may be a memory 62, such as a floppy disk, compact disk, or hard drive, that contains a computer program or data structure, for providing to a general purpose computer instructions and data for carrying out the functions of the previous embodiments.

The memory savings of the invention is illustrated in FIGS. 10(a-c), which lists 140 individual data points, and FIG. 11, which lists compressed nodes corresponding to the 140 data points of FIGS. 10(a-c). Prior to the invention, these data points would have been stored in 140 separate locations in memory, as shown in FIGS. 10(a-c). Each data point corresponds to a particular attribute (in this case attribute #10089), for a monitor of statistical data (in this case Model 40051a).

FIG. 11 shows the same data contained in FIGS. 10(a-c), but stored in accordance with the invention. The compressed file contains data stored with a 100% accuracy level, so that an exact reproduction of the original data is attained. In this instance, the figures following the term "compressed node" show the first data point in the node and the slope of the node. The final number represents one less than the number of data points in each compressed node.

Having thus described several particular embodiments of the invention, various alterations, modifications, and improvements will readily occur to those skilled in the art. These are intended to be within the spirit and scope of this invention. Accordingly, the foregoing description is by way of example only, and not intended to be limiting.