Patent Publication Number: US-2021175899-A1

Title: Error-bound floating point data compression system

Description:
BACKGROUND 
     Modern computing deployments generate tremendous amounts of data. Storage of this data consumes significant computing resources. Data compression techniques may be used to reduce the amount of stored data, and to therefore also reduce the resources required to store the data. 
     Data compression may be lossless, in which the original data can be reproduced exactly from compressed data, or lossy, in which exact reproduction of the original data from compressed data is not guaranteed. Lossy compression typically exhibits higher compression rates and/or faster processing than lossless compression. The compression technique to apply in a particular scenario depends on the error tolerance of the scenario as well on the type of data to be compressed. 
     Systems such as Internet-of-Things (IoT) architectures may produce floating point data. For example, an IoT sensor may provide temperature data which, after transformation from Celsius to Fahrenheit, is represented as a 64-bit double precision value. Compression of this data prior to storage is therefore desired. Moreover, due to the known accuracy limitations of the IoT sensor, it may be permissible to store these values such that decompression will result in a maximum error bound of 0.01 per value. 
     For example, it will be assumed that the values {1.241, 1.240, 1.239, 1.241, 1.253} are to be stored in view of an error bound of 0.01. According to a known approach for lossy floating point compression, the first four values are recognized as being within the error bound of a same value (i.e., 1.24) and the values are therefore stored as {4×1.24, 1×1.253} (e.g., as “run” array {4, 1} and “value” array {1.24, 1.253}). However, if consecutive values vary significantly with respect to the error bound (e.g., {1.2348903, 3.489345, −21.2344903, . . . }, the known approach stores the data as {1×1.2348903, 1×3.489345, 1×−21.2344903, . . . } (e.g., as “run” array {1, 1, 1, . . . } and “value” array {1.2348903, 3.489345, −21.2344903, . . . }), which fails to provide satisfactory compression. 
     Improvements to error-bound floating point compression are desired. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an architecture for generating, compressing, storing and retrieving floating point values according to some embodiments. 
         FIG. 2  is a tabular representation of floating point sensor values according to some embodiments. 
         FIG. 3  is a tabular representation of double precision versions of the  FIG. 2  sensor values according to some embodiments. 
         FIG. 4  is a flow diagram of a process to round floating point values based on an error bound according to some embodiments. 
         FIG. 5  is a tabular representation of rounded versions of the  FIG. 2  sensor values according to some embodiments. 
         FIG. 6  illustrates a processing pipeline for compressing floating point values according to some embodiments. 
         FIG. 7  illustrates a processing pipeline for compressing floating point values according to some embodiments. 
         FIG. 8  illustrates a processing pipeline for compressing floating point values according to some embodiments. 
         FIG. 9  is a flow diagram of a process to round floating point values based on an error bound and a total sum of values according to some embodiments. 
         FIG. 10  is a flow diagram of a process to round floating point values based on an error bound and a total sum of values according to some embodiments. 
         FIG. 11  is a block diagram of a computing system according to some embodiments. 
     
    
    
     DETAILED DESCRIPTION 
     The following description is provided to enable any person in the art to make and use the described embodiments and sets forth the best mode contemplated for carrying out some embodiments. Various modifications, however, will be readily-apparent to those in the art. 
     Embodiments relate to rounding each of a plurality of floating point values to a particular number of decimal places. Each of the rounded values is within a specified error-bound of its original value. The rounded values may then be subjected to further floating point compression, which in turn may include integer compression according to some embodiments. Some embodiments further operate to reduce or eliminate a difference in a sum total of error-bounded rounded values with respect to a sum total of corresponding original floating point values. 
     Some embodiments may therefore provide improved error-bound compression of input floating point values which exhibit, with respect to the error bound, a significant number of decimal places and/or large variances in consecutive values. 
       FIG. 1  illustrates architecture  100  according to some embodiments. Architecture  100  includes sensors  110   a - 110   d , each of which provides floating point values to stream processor  120 . Sensors  110   a - 110   d  may comprise any types and/or number of sensors, and may provide data to stream processor  120  on request, asynchronously, and/or according to any schedule or criteria. Stream processor  120  may comprise a processing component (e.g., an IoT hub) capable of receiving IoT data and processing it as desired. Embodiments are not limited to floating point values generated by sensors or processed by a stream processor. 
     According to the illustrated example, stream processor  120  transmits received floating point values to database platform  130  for storage. Stream processor  120  may compress the data as described herein prior to transmission to database platform. 
     Database platform  130  comprises database management system (DBMS)  132  and data store  134 . DBMS  132  may operate to compress data as described herein prior to storage in data store  134  and decompress thusly-stored data prior to providing the data to a requestor. DBMS  132  may also perform administrative and management functions for database platform  130 . Such functions may include snapshot and backup management, indexing, optimization, garbage collection, and/or any other database functions that are or become known. 
     Data store  134  may comprise any storage system for storing data in any format that is or becomes known. Data store  134  may include data of database tables and metadata describing the structure of the data, but embodiments are not limited thereto. The data of data store  134  may comprise one or more of conventional tabular data, row-based data, column-based data, and object-based data. Moreover, the data may be indexed and/or selectively replicated in an index to allow fast searching and retrieval thereof. 
     Database platform  130  may implement an “in-memory” database, in which a full database stored in volatile (e.g., non-disk-based) memory (e.g., Random Access Memory). The full database may be persisted in and/or backed up to fixed disks (not shown). Embodiments are not limited to an in-memory implementation. For example, data may be stored in Random Access Memory (e.g., cache memory for storing recently-used data) and one or more fixed disks (e.g., persistent memory for storing their respective portions of the full database). 
     Query server  140  may process Structured Query Language (SQL) and Multi-Dimensional eXpression (MDX) statements received from a database application (not shown). Processing may include generation of and execution of a query execution plan to retrieve data from data store  134 . As described above, DBMS  132  may decompress retrieved data prior to transmitting the data to query server  140 . 
       FIG. 2  is a tabular representation of floating point sensor values  200  which may be compressed according to some embodiments. Sensor values  200  may be received from any suitable source or sources, and embodiments are not limited to values generated by sensors. For purposes of comparison,  FIG. 3  is a tabular representation of double precision values  300  corresponding to sensor values  200  according to some embodiments. Embodiments may attempt to compress values such as sensor values  200  to a storage space of less than 64-bits per value, while maintaining a specified error bound. 
       FIG. 4  is a flow diagram of process  400  to round floating point values based on an error bound according to some embodiments. In some non-exhaustive embodiments, various hardware elements of a database system execute program code to perform process  400 . Process  400  and all other processes mentioned herein may be embodied in processor-executable program code read from one or more of non-transitory computer-readable media, such as a hard disk drive, a volatile or non-volatile random-access memory, a DVD-ROM, a Flash drive, and a magnetic tape, and then stored in a compressed, uncompiled and/or encrypted format. In some embodiments, hard-wired circuitry may be used in place of, or in combination with, program code for implementation of processes according to some embodiments. Embodiments are not limited to any specific combination of hardware and software. 
     Initially, a plurality of original floating point values are received at S 405 . The plurality of floating point values may be received or acquired from any source that is or becomes known. Each of the plurality of original floating point values may comprise a positive or a negative value and each of the plurality of original floating point values may include any number of decimal places. 
     According to some embodiments, also received at S 405  is an indication of an error bound, or quantization error. The error bound may indicate a maximum per-value error which may be exhibited by the values resulting from process  400 . Accordingly, S 405  may comprise reception of a command to compress a set of floating point values in view of a particular error bound. 
     In some embodiments, the component executing process  400  is aware of an applicable error bound. For example, in the case of architecture  100 , DBMS  132  may receive a command at S 405  to store a plurality of floating point values. DBMS  132  then independently determines to execute the remainder of process  400  to compress and store the floating point values in view of a predetermined error bound. 
     At S 410 , each of the plurality of original floating point values is rounded to a particular number (i.e., N) of decimal places. According to the presently-described example, N is initially set to a small number. Embodiments are not limited thereto, and these alternative embodiments will be described below. 
     More specifically, it will be assumed that the plurality of original floating point values are sensor values  200  of  FIG. 2 , the error bound is 0.01, and N is initially set to zero. At S 410 , each of sensor values  200  is rounded to value having zero decimal places. Accordingly, {1.24225, 1.25121, 1.2639, 1.2692} is rounded to {1, 1, 1, 1}. This rounding may be performed using a “scaling factor” according to some embodiments, such that rounded_value=round(original_value*scaling_factor)/scaling_factor. Using an initial scaling factor of 1 (which corresponds to N=0) at S 410 , rounded_value=round(1.24225*1)/1=1. 
     Next, at S 415 , it is determined whether each rounded value is within a specified error of its corresponding original value. Mathematically, for each original value, S 415  evaluates whether |original_value−rounded_value|&lt;0.01 is TRUE. With reference to the present example, S 415  determines whether |1.24225−1|&lt;0.01, |1.25121−1|&lt;0.01, |1.2639−1|&lt;0.01, |1.2692−1|&lt;0.01 are all TRUE. In other embodiments, S 415  may include determination of a maximum (original_value−rounded_value) and comparison of the maximum against the error bound. Int either case, and since none of the above inequalities are TRUE, the determination at S 415  in the above example is negative. 
     Flow proceeds to S 420  if the determination at S 415  is negative. At S 420 , it is determined whether N has reached a maximum prespecified value. S 420  provides an exit from process  400  in a case that the number of decimal points required to meet the error bound is greater than desired, or if one or more original values are such that the error bound cannot be met regardless of the number of decimal places to which the values are rounded (e.g., Inf). Accordingly, flow proceeds to S 435  to simply output the original floating point values if the determination at S 420  is positive. 
     If N has not yet reached the maximum prespecified value, flow proceeds from S 420  to S 425  to increment N. Each of the plurality of original floating point values is then rounded to the incremented number of decimal places at S 410 . 
     Assuming N is now equal to 1, the rounding may be performed at S 410  using a scaling factor of 10. For example, rounded_value=round(1.24225*10)/10=1.2, rounded_value=round(1.25121*10)/10=1.3, rounded_value=round(1.2639*10)/10=1.3, and rounded_value=round(1.2692*10)/10=1.3. Corresponding errors of each rounded value are {0.04225, 0.04879, 0.0361, 0.0308}. Since all of these values are greater than 0.01, the subsequent determination at S 415  is negative and flow returns to S 420 . 
     N is incremented at S 425  to 2, corresponding to a scaling factor of 100. Accordingly, at S 410 , rounded_value=round(1.24225*100)/100=1.24, rounded_value=round(1.25121*100)/100=1.25, rounded_value=round(1.2639*100)/100=1.26, and rounded_value=round(1.2692*100)/100=1.27. Corresponding errors of each rounded value are {0.00225, 0.00121, 0.0039, 0.0008}. It is therefore determined at S 415  that each rounded value is within 0.01 of its original value. 
     Flow proceeds from S 415  to S 430  to output the rounded values. With reference to the above example, the output values are {1.24, 1.25, 1.26, 1.27}.  FIG. 5  is a tabular representation of output rounded values  500  according to some embodiments. 
     As mentioned above, some embodiments of S 410  utilize a larger initial value (e.g., 20) for N. A positive determination at S 415  therefore causes N to be decremented and rounding to occur at S 410  based on the decremented value. Flow continues in this manner until the determination at S 415  is negative, in which case the output rounded values are those corresponding to the prior value of N (and corresponding scaling factor). 
     The output rounded floating point values may then be subjected to further compression. Use of the output rounded floating point values rather than the original floating point values may result in higher compression ratios than other lossy floating point compression techniques. 
       FIGS. 6 through 8  illustrate processing pipelines for compressing floating point values according to some embodiments. The illustrated pipelines may be implemented in any system in which floating point value compression is desired. Embodiments are not limited to the illustrated pipelines. 
     Pipeline  600  includes error-bound rounding component  610  to receive floating point values. Component  610  may execute process  400  upon the received floating point values to generate and output rounded floating point values as described above. Component  610  may also receive an error bound value for use in process  400 . Component  610  and each other component of  FIGS. 6 through 8  may comprise one or more processing units executing program code. 
     Floating point compression component  620  receives the rounded floating point values from rounding component  610  and performs compression to generate and output compressed floating point values. The compressed floating point values may be stored and/or transmitted as desired. Floating point compression component  620  may perform any type of floating point compression, lossless or lossy, that is or becomes known. 
     Pipeline  700  of  FIG. 7  may comprise a specific implementation of pipeline  600  according to some embodiments. Error-bound rounding component  710  may execute process  400  as described above. Integer conversion component  720  and integer compression component  730  may together perform floating point compression. For example, integer conversion component  720  may convert the rounded values output by rounding component  710  to integer values. Since the rounded values may each exhibit a same number of decimal places N, integer conversion component  720  may determine a scaling factor 10 N  which is then multiplied by each rounded value to generate a plurality of integer values. 
     The plurality of integer values and scaling factor are received by integer compression component  730 . Component  730  may compress the integer values using any integer compression algorithm that is or becomes known. The algorithm may comprise a combination of algorithms such as, but not limited to, but compression, run-length compression and delta compression. As is known, the combination may be dependent on the specific integer values being compressed and/or their relationship to one another. 
       FIG. 8  illustrates pipeline  800  including error-bound rounding component  810 , which may execute process  400  to generate a plurality of rounded floating point values. The rounded floating point values may be subjected to adaptive piecewise approximation by component  820  as described in the above Background. For example, if the rounded values output by component  810  are {1.241, 1.240, 1.239, 1.241, 1.253} and are to be lossy-compressed by component  820  with an error bound of 0.01, the values are output as “run” array {4, 1} and “value” array {1.24, 1.253}). The run array may then be subjected to integer compression by integer compression component  830  to generate a compressed run array, and the value array may be subjected to floating point compression by floating point compression component  840  to generate a compressed value array. The floating point compression of component  840  may proceed as described above with respect to components  720  and  730 , but embodiments are not limited thereto. 
       FIG. 9  a flow diagram of process  900  to round floating point values based on an error bound and a total sum of values according to some embodiments. Process  900  may be executed on the rounded values output by process  400  in some scenarios. For example, any of components  610 ,  710  and  810  described above may execute process  400  followed by process  900  to compress a plurality of floating point values based on an error bound and also on a total sum of the compressed values. 
     To illustrate the relevance of the total sum of values, consider the following plurality of values to be compressed: {1.24, 1.24, 1.24, 1.24, 1.24, 1.24, 1.24, 1.24, 1.24, 1.24}. The average value is 1.24 and the sum of the values is 12.4. Using process  400  to compress the values in view of an error bound of 0.1, the resulting rounded values would be {1.2, 1.2, 1.2, 1.2, 1.2, 1.2, 1.2, 1.2, 1.2, 1.2}, which have an average value of 1.2 and a total sum of 12. Accordingly, if the rounded values were stored in place of the original values, certain aggregate calculations on the stored data would result in different solutions than had they been performed on the original data. 
     The following rounded values are also within the error bound of 0.1 of the original values: {1.2, 1.2, 1.2, 1.2, 1.2, 1.2, 1.3, 1.3, 1.3, 1.3}. The average of these values is 1.24 and the sum is 12.4, as was the case with the original values. Accordingly, the second set of rounded values may be considered a closer representation of the original values in some scenarios. For example, certain aggregate calculations on the second set of rounded values may result in solutions more similar to those which would have been generated if the calculations were applied to the original values. 
     It will be assumed that, prior to process  900 , a plurality of original floating point values has been compressed to a plurality of rounded floating point values having N decimal places, for example by process  400 . Process  900  begins at S 905 , at which the values M and sum_approx are initialized to 1 and 0, respectively. 
     Next, at S 910 , the Nth decimal place of the Mth (i.e., first) rounded value is incremented to generate an incremented rounded value and decremented to generate a decremented rounded value. For example, assuming N=2 and the first rounded value is 1.23, the first incremented value is 1.24 and the first decremented value is 1.22. 
     At S 915 , one of the first rounded value, the first incremented value, and the first decremented value is selected. The selected value is the value which is within the error bound of the Mth original value and for which sum_approx+the selected value is closest to the sum of the first M original floating point values. In the case of the first iteration of S 915 , the selected value is simply the value which is within the error bound and closest to the first original value. Returning to the above example, if the original value was 1.2349 and the error bound is 0.01, then the first incremented value of 1.24 is within the error bound and the first decremented value of 1.22 is not. The difference between the first incremented value (1.24) and the original value (1.2349) is 0.0051, and the difference between the first rounded value (1.23) and the original value (1.2349) is 0.0049. Accordingly, the first rounded value (1.23) is selected at S 915 . 
     The selected value is added to sum_approx to generate a new running sum of the selected values. S 925  determines whether a next rounded value of the plurality of rounded values exists. If so, M is incremented by 1 at S 930  and flow returns to S 910  to increment the Nth decimal place of the Mth (i.e., second) rounded value to generate a second incremented rounded value and decrement the Nth decimal place of the Mth (i.e., second) rounded value to generate a second decremented rounded value. 
     S 915  proceeds as described above with respect to the second rounded, incremented and decremented values. One of these values is selected which is within the error bound of the second original value (the second rounded value will be within the error bound by virtue of process  400 ) and for which the new sum_approx+the selected value is closest to the sum of the first two original floating point values. Flow then proceeds to S 920  as described above. 
     Accordingly, flow cycles from S 910  through S 930  until it is determined at S 925  that the last rounded value of the plurality of rounded values has been processed. Next, at S 935 , each of the M values selected during the M iterations of S 915  is output. As described above, the output values will be within an error bound of their corresponding original values, and a sum of the original values may be closer to a sum of the output values than to a sum of the rounded values input to process  900 . 
       FIG. 10  is a flow diagram of process  1000  to round floating point values based on an error bound and a total sum of values according to some embodiments. Unlike process  900 , the sum of the output values of process  1000  is intended to be equal to a sum of the original plurality of non-rounded floating point values. 
     For a given plurality of rounded input values V, process  1000  selects the same values at S 1015  as selected at S 915  of process  900  for the first through V−1 values. However, upon determining at S 1025  that a last rounded value V remains to be processed, flow continues to S 1035 . At S 1035 , a value is determined for which the sum of all selected values will be equal to the sum of the plurality of original floating point values. In other words, the determined value is the differences between the sum of the plurality of original floating point values and the then-current sum_approx. The selected M values and the value determined at S 1035  are output at S 1040 . 
     The value determined at S 1035  may comprise any number of decimal places and may be stored as a different type (e.g., double-precision) and subjected to different compression than the output selected M values. In a case that process  400 + 1000  is run on blocks of 10,000 input values, one such correction value is stored for every 10,000 entries. 
       FIG. 11  is a block diagram of database system  1100  according to some embodiments. Database system  1100  may comprise a general-purpose computing apparatus and may execute program code to perform any of the functions described herein. Database system  1100  may comprise an implementation of database platform  130  in some embodiments. Database system  1100  may include other unshown elements according to some embodiments. 
     Database system  1100  includes processing unit(s)  1110  operatively coupled to I/O device  1120 , data storage device  1130 , one or more input devices  1140 , one or more output devices  1150  and memory  1160 . I/O device  1120  may facilitate communication with external devices, such as a streaming hub, a client device, or a data storage device. Input device(s)  1140  may comprise, for example, a keyboard, a keypad, a mouse or other pointing device, a microphone, knob or a switch, an infra-red (IR) port, a docking station, and/or a touch screen. Input device(s)  1140  may be used, for example, to enter information into system  1100 . Output device(s)  1150  may comprise, for example, a display (e.g., a display screen) a speaker, and/or a printer. 
     Data storage device  1130  may comprise any appropriate persistent storage device, including combinations of magnetic storage devices (e.g., magnetic tape, hard disk drives and flash memory), optical storage devices, Read Only Memory (ROM) devices, etc., while memory  1160  may comprise Random Access Memory (RAM). 
     The database applications, query server and database management system of data storage device may each comprise program code executed by processing unit(s)  1110  to cause system  1100  to perform any one or more of the processes described herein. Embodiments are not limited to execution of these processes by a single computing device. 
     Data stored in device  1130  may include database tables as is known. Database tables (either cached or a full database) may be stored in volatile memory such as volatile memory  1160 . Data storage device  1130  may also store data and other program code for providing additional functionality and/or which are necessary for operation of system  1100 , such as device drivers, operating system files, etc. 
     The foregoing diagrams represent logical architectures for describing processes according to some embodiments, and actual implementations may include more or different components arranged in other manners. Other topologies may be used in conjunction with other embodiments. Moreover, each component or device described herein may be implemented by any number of devices in communication via any number of other public and/or private networks. Two or more of such computing devices may be located remote from one another and may communicate with one another via any known manner of network(s) and/or a dedicated connection. Each component or device may comprise any number of hardware and/or software elements suitable to provide the functions described herein as well as any other functions. For example, any computing device used in an implementation some embodiments may include a processor to execute program code such that the computing device operates as described herein. 
     Embodiments described herein are solely for the purpose of illustration. Those in the art will recognize other embodiments may be practiced with modifications and alterations to that described above.