Querying compressed time-series signals

• US 8,219,574 B2
• Filed: 06/22/2009
• Issued: 07/10/2012
• Est. Priority Date: 06/22/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Jie, Nath, Suman Kumar, Zhao, Feng, Reeves, Galen Andrew, Gandhi, Sorabh Kumar
• Primary Examiner(s): Lu, Kuen
• Assistant Examiner(s): Pham, Tuan A
• Application Number:
  US12/488,598
• Publication Number:
  US 20100325132A1
• Time in Patent Office: 1,114 Days
• Field of Search: 707/713, 707759-766, 707769-779
• 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 executed by a computer processor, the method comprising:

receiving a query for execution with respect 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, 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 query over at least one of the first time-series signal, the second time-series signal, or the third time-series signal, 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.

2. 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.

3. The method of claim 2, 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.

4. The method of claim 3, 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.

5. The method of claim 4, 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.

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

7. The method of claim 3, 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.

8. 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.

9. The method of claim 8, 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.

10. 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.

11. A system comprising:

a processor; and

a memory that comprises a plurality of components that are executed by the processor, the plurality of components comprising;

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

a query executor component that selectively executes the query over at least one of multiple available compressed representations of the raw time-series signal, the multiple available compressed representations of the raw time-series signal comprising;

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, 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, wherein the query executor component selects the at least one of the multiple available compressed representations of the raw time-series signals for executing the query thereover based upon whether the query pertains to determining the trend, generating the histogram, or determining the correlation, 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.

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

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

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

15. A computer-readable data storage device 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.