Compression of non-dyadic sensor data organized within a non-dyadic hierarchy

Sensors organized into hierarchies are used in a variety of real-world environments. For example, a data center may include a number of server computing devices, or servers, arranged in racks within locations spread around the world. The servers may each be equipped with sensors that monitor the air temperature inlet into the server and the air temperature exhausted from the server. The servers are organized within a hierarchy in that the servers may be organized by location, and within each location, by rack. Other examples of hierarchical sensors include sensors that detect stock prices of stocks organized by sectors, company size, and/or geographical location, as well as geo-spatial sensors that detect various earth conditions, such as barometric pressure, air temperature, and so on.

FIG. 1 is a diagram of a system, according to an embodiment of the disclosure.

FIG. 2 is a diagram of exemplary non-dyadic sensor data organized within a non-dyadic hierarchy, according to an embodiment of the disclosure.

FIG. 3 is a flowchart of a method, according to an embodiment of the disclosure.

FIG. 4 is a flowchart of a method for generating a wavelet basis matrix, according to an embodiment of the disclosure.

FIG. 5 is a flowchart of a method for generating a coefficient matrix, according to an embodiment of the disclosure.

FIG. 6 is a diagram of a representative computing device, according to an embodiment of the disclosure.

As noted in the background section, hierarchical sensors are used in a variety of real-world environments. Such sensors generate sensor data, which is also hierarchical in correspondence to the hierarchy of the sensors themselves. Because of the vast amount of sensor data that may be generated, it is useful to compress the sensor data before processing, where such processing may include the storage of the sensor data, for instance.

Sensor data is typically non-dyadic, in that the sensor data is organized within hierarchies that are non-dyadic. By comparison, dyadic sensor data is sensor data that is organized within a dyadic hierarchy. Sensor data is dyadic where the data has a length (i.e., a number of leaves within a corresponding hierarchical tree within which the data is organized) equal to 2 k , where kεN and where N is a set of all non-negative integers. A hierarchy that organizes sensor data over a number of hierarchical subsets is dyadic where each subset has a length equal to 2 h , where hεN. Non-dyadic sensor data is therefore sensor data that does not have a length equal to 2 k , and a hierarchy of sensor data that organizes the data over a number of hierarchical subsets is non-dyadic where at least one subset does not have a length equal to 2 h .

The inventors have developed a novel approach to compress sensor data that is organized within a non-dyadic hierarchy. In particular, a discrete wavelet transform is generated based on the sensor data and the hierarchy of the sensor data to compress the sensor data. As such, hierarchical sensor data that is not dyadic, and that has a hierarchy that is not dyadic, can nevertheless be compressed. In this respect, the inventive approach is advantageous over existing approaches, such as the Haar wavelet approach, which can only compress dyadic sensor data organized within a dyadic hierarchy.

FIG. 1 shows a system 100 , according to an embodiment of the disclosure. The system 100 includes a number of sensors 102 A, 102 B, . . . , 102 N, collectively referred to as the sensors 102 . The system 100 further includes a receiving component 104 , a compression component 106 , and a processing component 108 . The components 104 , 106 , and 108 may each be implemented in software, hardware, or a combination of software and hardware. For instance, each component may be implemented as one or more computer programs stored on a computer-readable medium and that are executable by one or more processors of one or more computing devices.

The receiving component 104 receives sensor data collected by the sensors 102 . The term sensor is used herein in a broad and non-limiting sense. For example, a sensor may detect real-world data, such as temperature, humidity, and so on. As another example, a sensor may be considered as detecting stock prices, number of instructions processed per processor cycle, and so on. These examples illustrate the wide variety of the types of sensors 102 and the types of sensor data that are amenable to embodiments of the present disclosure.

The receiving component 104 transmits the sensor data to the compression component 106 , which thus receives the sensor data from the receiving component 104 . The sensor data is denoted as y, as indicated by the arrow 110 . The sensor data includes a number of individual data elements y k . The compression component 106 compresses the sensor data by generating a discrete wavelet transform based on the sensor data and based on a hierarchy of the sensor data. The compressed sensor data is denoted as H, b, as indicated by the arrow 112 .

It is noted that the sensor data y can be represented as:

y=H′b

In this equation, H is a wavelet basis matrix, b is a coefficient matrix, and the operator “′” represents the conjugate transpose of a matrix. Thus, by generating a discrete wavelet transform represented by H and b, the compression component 106 compresses the sensor data received from the receiving component 104 .

The compression component 106 transmits the compressed sensor data, specifically the discrete wavelet transform as represented by H and b, to the processing component 108 , which thus receives the compressed sensor data from the compression component 106 . The processing component 108 then processes the sensor data as has been compressed. As a rudimentary example, the processing component 108 may simply store the compressed sensor data on a non-volatile computer-readable medium, such as a magnetic medium like a hard disk drive.

More specifically, the result of compressing the sensor data is coefficient matrix b, where for sensor data that has a fixed hierarchy, the wavelet basis matrix is determined once. For all new sensor data, the coefficient matrix b is determined, and part of this coefficient matrix is stored as the compressed sensor data itself. For example, if there are 1,000 sensors generating 1,000 sensor data points, a small set of values of the coefficient matrix b may be stored. For instance, if just 10 values of the coefficient matrix b are stored, then 99% compression is achieved.

FIG. 2 shows exemplary non-dyadic sensor data 200 organized within a non-dyadic hierarchy 204 , according to an embodiment of the disclosure. The sensor data 200 includes nine individual data elements 208 A, 208 B, . . . , 208 I, which are collectively referred to as the data elements 208 , and which correspond to the individual data elements y 1 , y 2 , . . . y 9 . The sensor data 200 is non-dyadic, because the data 200 has a length unequal to 2 k , where kεN and where N is a set of all non-negative integers. That is, the number of data elements 208 within the sensor data 200 is equal to 9, and there is no non-negative integer k for which 2 k =9.

The hierarchy 204 within which the sensor data 200 is organized has six hierarchical levels 202 A, 202 B, 202 C, 202 D, 202 E, and 202 F, collectively referred to as the hierarchical levels 202 . The top-most, or highest, level 202 A includes a subset 206 A of all the data elements 208 . The second level 202 B divides the set 206 A into the subset 206 B having the data elements y 1 , y 2 , . . . , y 8 and the individual data element y 9 . The third level 202 C divides the subset 206 B into a subset 206 C having the data elements y 1 , y 2 , y 3 , and a subset 206 D having the data elements y 4 , y 5 , . . . , y 8 . The fourth level 202 D divides the subset 206 C into the individual data element y 1 and a subset 206 E having the data elements y 2 , y 3 , and divides the subset 206 D into a subset 206 F having the data elements y 4 , y 5 and a subset 206 G having the data elements y 6 , y 7 , y 8 . The fifth level 202 E divides the subset 206 E into the individual data elements y 2 and y 3 , the subset 206 F into the individual data elements y 4 and y 5 , and the subset 206 G into the individual data element y 6 and a subset 206 H having the data elements y 7 , y 8 . Finally, the bottom-most, or lowest, level 202 F divides the subset 206 H into the individual data elements y 7 and y 8 .

Each given subset is thus divided into two nodes, where each node is a smaller subset than the given subset or a single data element. The hierarchy 204 is constructed in a bottom-up manner, from the individual data elements. The hierarchy 204 is used to construct the wavelet basis matrix H. By comparison, the coefficient matrix b can be constructed from the wavelet basis matrix H or from the hierarchy 204 itself.

The subsets 206 A, 206 B, . . . , 206 H over which the hierarchical levels 202 organize the sensor data 200 are referred to as the subsets 206 , and are themselves hierarchical in correspondence with the levels 202 in which they are located. The hierarchy 204 is non-dyadic, because at least one of the hierarchical subsets 206 has a length unequal to 2 h , where hεN and where N is a set of all non-negative integers. That is, at least one of the hierarchical subsets has a length f for which there is no non-negative integer k for which 2 k =f.

The individual data elements 208 are organized within the hierarchical subsets 206 of the hierarchical levels 202 of the hierarchy 204 by what are referred to as a series of intervals. Each interval includes the individual data elements within subset j of level i, where the subsets within each level are numbered starting at j=1 with the subset at the left-hand side in FIG. 2 . In this sense, each subset is an interval. The data elements within subset j of level i are referred to as S i,j .

The individual data elements 208 are thus organized within a series of intervals, starting from the subset of a bottom-most level that has a subset, which in this example is the level 202 E because the level 202 F does not have any subsets, and proceeding to the subset of the top-most level 202 A. Within each such level, the series of intervals is ordered from the first subset of the level to the last subset of the level, if the level in question has more than one subset. Therefore, for the example in FIG. 2 , the individual data elements 208 are organized within the series of intervals: {y 7 , y 8 }, {y 2 , y 3 }, {y 4 , y 5 }, {y 6 , y 7 , y 8 }, {y 1 , y 2 , y 3 }, {y 4 , y 5 , . . . , y 8 , }, {y 1 , y 2 , . . . , y 8 }, and {y 1 , y 2 , . . . , y 9 }, which correspond to the subsets 206 H, 206 E, 206 F, 206 G, 206 C, 206 D, 206 B, and 206 A, respectively.

Furthermore, the number of elements at level i, interval j is denoted as n i,j =|S i,j |. For example, for hierarchical level 202 A, which is level 0, the elements y within this level are S 0,1 , and the number of the elements y within this level is equal to n 0,1 =|S 0,1 |. As another example, for hierarchical level 202 C, which is level 2, the elements within this level are S 2,1 ∪S 2,2 , and the number of elements within this level is equal to n 2,1 +n 2,2 =|S 2,1 +|S 2,2 |. As a final example, the elements within the subset 206 D of the level 202 C, which is interval 2 of level 2, are equal to the union of the elements within the subsets 206 F and 206 G of the level 202 D, which are intervals 2 and 3 of level 3. That is, S 2,2 =S 3,2 ∪S 3,3 , and n 2,2 =|S 2,2 |=n 3,2 +n 3,3 |S 3,2 |+|S 3,3 |.

FIG. 3 shows a method 300 , according to an embodiment of the disclosure. As with other embodiments of the disclosure, the method 300 may be implemented as one or more computer programs stored on a computer-readable medium. Execution of the computer programs by one or more processors of one or more computing devices results in performance of the method 300 . The computer-readable medium may be a volatile medium, such as volatile semiconductor memory, or a non-volatile medium, such as a non-volatile magnetic medium like a hard disk drive, or such as a non-volatile semiconductor memory like flash memory. As such, each part of the method 300 may be considered as being performed by a processor of a computing device in one embodiment.

Sensor data is received from one or more sensors ( 302 ). The sensor data is organized within a hierarchy. Both the sensor data and the hierarchy are non-dyadic. The sensor data y may be received by the receiving component 104 of FIG. 1 from the sensors 102 of FIG. 1 . The receiving component 104 in this case then sends the sensor data y to the compression component 106 of FIG. 1 .

A discrete wavelet transform is generated, based on the sensor data and based on the hierarchy of the sensor data, to compress the sensor data ( 304 ). The discrete wavelet transform is represented by the wavelet basis matrix H and the coefficient matrix b, as described above, such that the discrete wavelet transform is equal to H′b. The compression component 106 of FIG. 1 may generate the discrete wavelet transform, which represents a compression of the sensor data y. The compression component 106 sends the wavelet basis matrix H and the coefficient matrix b to the processing component 108 of FIG. 1 . In particular, just some of the values of the coefficient matrix b may be selected as representing the compression of the sensor data y.

Generation of the discrete wavelet transform in part 304 includes the following. The wavelet basis matrix H is generated ( 306 ), and the coefficient matrix b is also generated ( 308 ). The order in which the wavelet basis matrix and the coefficient matrix are generated is not important, and the two matrices can indeed be generated simultaneously if desired. As noted above, for a fixed hierarchy the wavelet basis matrix H is generated just once. The manner by which the wavelet basis matrix H can be generated, and the manner by which the coefficient matrix b can be generated, are described later in the detailed description.

The sensor data, as has been compressed via generation of the discrete wavelet transform, is then processed ( 310 ). For example, the compressed sensor data—i.e., the wavelet basis matrix H and the coefficient matrix b—can be stored on a non-volatile computer-readable medium for later retrieval. The compressed sensor data can also be processed in other ways besides storage. For example, the compressed sensor data can be examined to discern trends in the sensor data, to determine whether any critical conditions have occurred as represented by the sensor data, and so on. The processing component 108 of FIG. 1 can perform part 310 .

FIG. 4 shows a method 400 for generating the wavelet basis matrix H in part 306 of the method 300 of FIG. 3 , according to an embodiment of the disclosure. The wavelet basis matrix H is a square matrix having the size z×z. As such, the wavelet basis matrix has a number of row vectors H l , where 0≦l<z. Furthermore, each row vector H l has a number of individual elements H l,m , where 0≦m<n.

The first row vector H 0 of the wavelet basis matrix H is generated ( 402 ). This is achieved by populating each individual element H 0,m within the first row vector H 0 with a value of one ( 404 ). As such, the first row vector H 0 is equal to {1, 1, . . . , 1}. The first row vector H 0 is said to correspond to the approximation coefficient(s) of the coefficient matrix b, the generation of which is described later in the detailed description.

All the other row vectors H l , 0<l<z, of the wavelet basis matrix H are then generated ( 406 ). This is achieved by generating each individual element H l,m within each such row vector H l ( 408 ), as follows:

H I , m = { ( n ⁢ 1 2 ⁢ n a + n b n a ⁢ n b ) ⁢ 2 ⁢ ⁢ n b n a + n b if ⁢ ⁢ y m ∈ S i + 1 , j - ( n ⁢ 1 2 ⁢ n a + n b n a ⁢ n b ) ⁢ 2 ⁢ ⁢ n b n a + n b if ⁢ ⁢ y m ∈ S i + 1 , j + 1 0 otherwise

As noted above, y is the set of the sensor data, y m is an individual element of the set of the sensor data, and there are n total individual elements y m within the set of sensor data. Each level i of the hierarchy has an interval j of individual elements of the sensor data, and the individual elements at level i and interval j are denoted by S i,j . The row vectors H l , 0<l<z, are said to correspond to the detail coefficients of the coefficient matrix b, the generation of which is described later in the detailed description. Furthermore, n a is a number of points in a left child node of the individual element H l,m , and n b is a number of points in a right child node of the individual element H l,m

FIG. 5 shows a method 500 for generating the coefficient matrix b in part 308 of the method 300 of FIG. 3 , according to an embodiment of the disclosure. The coefficient matrix b includes one or more approximation coefficients and more than one detail coefficient. For a given interval S i,j , the approximation coefficient is referred to as a i,j , and the detail coefficient is referred to as c i,j .

In general, the approximation coefficients provide a general approximation of the sensor data upon the sensor data being compressed. The approximation coefficients corresponding to the lowest level of the hierarchy within which the sensor data has been organized represent averages of successive values of the sensor data. The approximation coefficients corresponding to the other, higher levels of the hierarchy represent averages of successive approximation coefficients of lower levels of the hierarchy.

Furthermore, in general, the detail coefficients provide a level of detail of the sensor data upon the sensor data being compressed. The detail coefficients corresponding to the lowest level of the hierarchy represent differences between successive values of the sensor data. The detail coefficients corresponding to the other, higher levels of the hierarchy represent differences of the approximation coefficients of lower levels of the hierarchy.

The method 500 generates the coefficients for the coefficient matrix b ( 502 ), by generating the approximation coefficients ( 504 ), and by generating the detail coefficients ( 506 ). Each approximation coefficient is generated in part 504 as follows:

a i , j = ∑ k ∈ S i , j ⁢ ⁢ y k  S i , j 

Furthermore, each detail coefficient is more specifically generated in part 506 as follows:

c i , j = a i + 1 , k - a i + 1 , k + 1 2 = ∑ m ∈ S i + 1 , k ⁢ ⁢ y m  S i + 1 , k  - ∑ m ∈ S i + 1 , k + 1 ⁢ ⁢ y m  S i + 1 , k + 1  2

As noted above, a i,j is an approximation coefficient, and c i,j is a detail coefficients. Furthermore, y is the set of the sensor data, y k is an individual element of the set of the sensor data, and there is a total of n individual elements y k within the set of the sensor data. Each level i of the hierarchy has an interval j of individual elements of the sensor data, and the individual elements at level i and interval j are denoted by S i,j .

The method 500 then normalizes the approximation coefficients and the detail coefficients that have been generated ( 508 ). Normalization is achieved so that the wavelet matrix H is such that HH′=nl, where l is the identity matrix, and as before, n is the number of individual data elements y k within the sensor data y. Each approximation coefficient can be normalized as follows:

a i , j = ( 1 n ) ⁢ (  S i , j  ) ⁢ a i , j

Furthermore, each detail coefficient can be normalized as follows:

The method 500 finally generates the coefficient matrix b by using the approximation coefficients and the detail coefficients that have been generated and normalized ( 510 ). For the sensor data y, the coefficient matrix b has n coefficients, equal to the number of individual data elements y k within the sensor data y. The first coefficient within the coefficient matrix b is selected as the approximation coefficient a 0,1 . The remaining n−1 coefficients of the coefficient matrix b are selected as the detail coefficients, starting from the detail coefficient of the first level of the hierarchy, and continuing towards the last detail coefficient of the last level of the hierarchy, until n−1 detail coefficients have been chosen. As such, the coefficient matrix b can be expressed as:

b={a 0,1 ,c 0,1 ,c 1,1 ,c 1,2 , . . . }′

In conclusion, FIG. 6 shows a rudimentary and representative computing device 600 , according to an embodiment of the disclosure. The computing device 600 includes one or more processors 602 and one or more computer-readable media 604 . The computing device 600 may include other hardware, in addition to the processors 602 and the computer-readable media 604 . The computer-readable media 604 stores one or more computer programs 606 that are executable by the processors 602 . The computer-readable medium 604 may be volatile and/or non-volatile media, such as volatile and/or non-volatile semiconductor memory, non-volatile magnetic media, and so on.

The compression component 106 is specifically depicted in FIG. 6 as being implemented by the computer programs 606 as executed by the processors 602 . The other components of the system 100 of FIG. 1 , such as the receiving component 104 and/or the processing component 108 , may be implemented in the same way as the compression component 106 . In particular, the components 104 and 108 may be implemented on the same computing device 600 as the compression component 106 , or on one or more different computing devices. In the latter case, the various computing devices, including the computing device 600 , communicate with one another, such as over a network.