QUERYING COMPRESSED TIME-SERIES SIGNALS

• US 20100325132A1
• Filed: 06/22/2009
• Published: 12/23/2010
• Est. Priority Date: 06/22/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Reeves, Galen Andrew, Gandhi, Sorabh Kumar, Zhao, Feng, Liu, Jie, Nath, Suman Kumar
• Granted Patent: US 8,219,574 B2
• Time in Patent Office: Days
• US Class Current: 707/759
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

A system described herein includes a receiver component that receives a query that pertains to a raw time-series signal. A query executor component selectively executes the query over at least one of multiple available compressed representations of the raw time-series signal, wherein the query pertains to at least one of one of determining a trend pertaining to the raw time-series signal, generating a histogram pertaining to the raw time-series signal, or determining a correlation pertaining to the raw time-series signal.

Claims

1. A method comprising the following computer-executable acts:

receiving a query for execution with respect to at least one raw time-series signal;

accessing a data repository that comprises at least three time-series signals that are based at least in part upon the raw time-series signal, wherein the at least three time-series signals are compressions of the raw time-series signal, wherein the at least three time-series signals include;

a first time-series signal that is based at least in part upon execution of a low-pass filter over the raw time-series signal;

a second time-series signal that is based at least in part upon a difference between the raw time-series signal and the first time-series signal; and

a third time-series signal that is representative of frequencies in the raw time-series data that are existent in the raw time-series signal but lacking in the first time-series signal and the second time-series signal; and

selectively executing the received query over at least one of the first time-series signal, the second time-series signal, or the third time-series signal.

2. The method of claim 1, wherein the received query pertains to one of determining a trend pertaining to the raw time-series signal, generating a histogram pertaining to the raw time-series signal, or determining a correlation pertaining to the raw time-series signal.

3. The method of claim 2, wherein if the query is for determining the trend pertaining to the raw time-series signal, the query is executed over the first time-series signal, and wherein if the query is for generating the histogram pertaining to the raw time-series signal, the query is executed over the first time-series signal.

4. The method of claim 1, further comprising:

receiving the raw time-series signal; and

generating the first time-series signal, the second time-series signal, and the third time-series signal.

5. The method of claim 4, wherein generating the first time-series signal comprises:

passing the raw time-series data through a low-pass filter to generate a filtered signal; and

downsampling the filtered signal to generate the first time-series signal.

6. The method of claim 5, wherein generating the second time-series signal comprises:

subtracting the filtered signal from the raw time-series signal to generate a remainder signal;

removing samples in the remainder signal that have a value that is below a predefined threshold to generate the second time-series signal.

7. The method of claim 6, wherein generating the third time-series signal comprises:

compressing a residual of the raw time-series signal to generate the third time-series signal, wherein the residual of the raw time-series signal is the second time-series signal and the filtered signal subtracted from the raw time-series signal.

8. The method of claim 7, wherein random projection is utilized in connection with compressing the residual of the raw time-series signal.

9. The method of claim 5, wherein passing the raw time-series data through the low-pass filter to generate a filtered signal comprises a Fast Fourier Transform on the raw time-series signal and retaining a threshold a threshold number of coefficients of the Fast Fourier Transform.

10. The method of claim 1, further comprising:

utilizing piecewise linear approximation to compress at least one of the first time-series signal, the second time-series signal, or the third time-series signal to generate a compressed signal;

including the compressed signal into a group of similar time-series signals, wherein the group of similar time-series signals comprises a base signal;

generating a ratio signal between the compressed signal and the base signal;

representing signals in the group of similar time-series signals with the base signal and ratio signals; and

utilizing a multiple skip list index in connection with storing the ratio signal.

11. The method of claim 10, further comprising:

receiving a query for execution over a portion of the compressed signal;

utilizing the multiple skip list index to locate a portion of the ratio signal that corresponds to the portion of the compressed signal;

regenerating the portion of the compressed signal by multiplying a portion of the base signal that corresponds to the portion of the compressed signal with the portion of the ratio signal; and

executing the query over the portion of the compressed signal.

12. The method of claim 1, further comprising receiving an indication from an issuer of the query pertaining to which of the first time-series signal, the second time-series signal, or the third time-series signal is to be accessed when executing the query.

13. A system that comprises the following computer-executable components:

a receiver component that receives a query that pertains to a raw time-series signal;

a query executor component that selectively executes the query over at least one of multiple available compressed representations of the raw time-series signal, wherein the query pertains to at least one of determining a trend pertaining to the raw time-series signal, generating a histogram pertaining to the raw time-series signal, or determining a correlation pertaining to the raw time-series signal.

14. The system of claim 13, wherein the multiple available compressed representations of the raw time-series signal comprises a first time-series signal that is generated at least in part by passing the raw time-series signal through a low-pass filter.

15. The system of claim 14, wherein the first time-series signal is generated by way of downsampling an output of the low-pass filter.

16. The system of claim 14, wherein the multiple available compressed representations of the raw time-series signal comprises a second time-series signal that is generated based at least in part upon a determined difference between an output of the low-pass filter and the raw time-series signal.

17. The system of claim 16, wherein the multiple available compressed representations of the raw time-series signal comprises a third time-series signal that is generated based at least in part upon a determined difference between the output of the low-pass filter plus the second time-series signal and the raw time-series signal.

18. The system of claim 17, wherein the third time-series signal is compressed through utilization of a random projection.

19. The system of claim 14, wherein the raw time-series signal is representative of data obtained from a data center.

20. A computer-readable medium comprising instructions that, when executed by a processor, cause the processor to perform the following acts:

receive a query pertaining to a raw time-series signal, wherein the query pertains to one of determining a trend pertaining to the raw time-series signal, generating a histogram pertaining to the raw time-series signal, or determining a correlation pertaining to the raw time-series signal;

accessing a data repository that comprises at least three time-series signals that are based at least in part upon the raw time-series signal, wherein the at least three time-series signals are compressions of the raw time-series signal, and wherein the at least three time-series signals include;

a first time-series signal, wherein the first time-series is generated by;

passing the raw time-series data through a low-pass filter to generate a filtered signal; and

downsampling the filtered signal to generate the first time-series signal;

a second time-series signal, wherein the second time-series signal is generated by;

subtracting the filtered signal from the raw time-series signal to generate a remainder signal; and

removing samples in the remainder signal that have a value that is below a predefined threshold to generate the second time-series signal; and

a third time-series signal, wherein the third time-series signal is generated by compressing a residual of the raw time-series signal to generate the third time-series signal, wherein the residual of the raw time-series signal is the second time-series signal and the filtered signal subtracted from the raw time-series signal; and

selectively executing the query over one of the first time-series signal, the second time-series signal, or the third time-series signal to cause output results to be displayed on a display screen of a computing device.