Querying compressed time-series signals

• US 8,655,887 B2
• Filed: 06/08/2012
• Issued: 02/18/2014
• 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): Mahmoudi, Tony
• Assistant Examiner(s): Pham, Tuan A
• Application Number:
  US13/491,838
• Publication Number:
  US 20120246169A1
• Time in Patent Office: 620 Days
• Field of Search: None
• US Class Current: 707/741
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

Technologies pertaining to compressing time-series signals are described herein. Groups of time-series signals are generated based upon similarities between time-series signals. Each group of time-series signals includes a respective base time-series signal. Ratio signals that are representative of time-series signals are computed, wherein the ratio signals are based upon the base time-series signal and other respective time-series signals in a group of time-series signals.

Claims

1. A method comprising the following computer-executable acts, the method executed by a processor of a computing device, the method comprising:

receiving a plurality of time-series signals of a first signal type, each time-series signal in the plurality of time-series signals of the first signal type being a compression of a respective raw time-series signal from amongst a plurality of raw time-series signals, the first signal type representing respective low frequency portions of the plurality of raw time-series signals or respective high frequency portions of the plurality of raw time-series signals;

generating respective identifiers for each of the plurality of time-series signals of the first signal type;

selecting a representative time-series signal for the plurality of time-series signals of the first signal type from amongst the plurality of time-series signals;

computing ratio signals for respective time-series signals in the plurality of time-series signals relative to the representative time-series signal; and

generating a computer-readable index in a data repository that indexes the ratio signals by the respective identifiers, wherein a time-series signal identified in the computer-readable index is reconstructable based at least in part upon the representative time-series signal and the ratio signal for the time-series signal.

2. The method of claim 1, the first signal type representing respective anomalies resident in the plurality of raw time-series signals.

3. The method of claim 1, further comprising:

receiving a plurality of time-series signals of a second signal type, each time-series signal in the plurality of time-series signals of the second signal type being a compression of a respective raw time-series signal from amongst the plurality of raw time-series signals;

generating respective second identifiers for each of the plurality of time-series signals of the second signal type;

selecting a second representative time-series signal for the plurality of time-series signals of the second signal type from amongst the plurality of time-series signals of the second type;

computing second ratio signals for respective time-series signals in the plurality of time-series signals of the second signal type relative to the second representative time-series signal; and

generating a second computer-readable index in the data repository that indexes the second ratio signals by the respective second identifiers, wherein a second time-series signal identified in the computer-readable index is reconstructable based at least in part upon the second representative time-series signal and the ratio signal for the second time-series signal.

4. The method of claim 3, further comprising:

receiving a plurality of time-series signals of a third signal type, each time-series signal in the plurality of time-series signals of the third signal type being a compression of a respective raw time-series signal from amongst the plurality of raw time-series signals;

generating respective third identifiers for each of the plurality of time-series signals of the third signal type;

selecting a third representative time-series signal for the plurality of time-series signals of the third signal type from amongst the plurality of time-series signals of the third type;

computing third ratio signals for respective time-series signals in the plurality of time-series signals of the third signal type relative to the third representative time-series signal; and

generating a third computer-readable index in the data repository that indexes the third ratio signals by the respective third identifiers, wherein a third time-series signal identified in the third computer-readable index is reconstructable based at least in part upon the third representative time-series signal and the ratio signal for the third time-series signal.

5. The method of claim 4, further comprising:

receiving a query of a particular type;

selectively accessing one of the computer-readable index, the second computer-readable index, or the third computer-readable index based upon the particular type of the query.

6. The method of claim 5, wherein the query comprises data that identifies a time-series signal over which the query is to be executed, and further comprising:

reconstructing the time-series signal based at least in part upon a respective ratio signal corresponding to the time-series signal and a representative signal in the one of the accessed computer-readable index, the second computer-readable index, or the third computer-readable index; and

executing the query over the time-series signal subsequent to the time-series signal being reconstructed.

7. The method of claim 5, wherein the particular type of the query is one of a query for determining a trend pertaining to a trend pertaining to a raw time-series signal, a query for determining a histogram pertaining to the raw time-series signal, or a query for determining a correlation pertaining to the raw time-series signal.

8. The method of claim 7, wherein if the query is for determining the trend pertaining to the raw time-series signal, the computer-readable index is accessed, and wherein if the query is for generating the histogram pertaining to the raw time-series signal, the computer-readable index is accessed.

9. The method of claim 1, wherein the plurality of raw time-series signals are representative of processor utilization of servers in a data center.

10. 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 signal compressor component that receives a plurality of time-series signals that are retained in a data repository, the signal compressor compressing each time series-signal in the plurality of time-series signals to generate a respective plurality of compressed time-series signals, the signal compressor component storing the plurality of compressed time-series signals in the data repository;

a grouper component that receives the plurality of compressed time-series signals from the data repository and generates a plurality of sub-groups of compressed time-series signals, wherein, for each sub-group of compressed time-series signals, the grouper component selects a respective base time-series signal; and

a ratio determiner component that, for each sub-group of compressed time-series signals, generates a respective ratio signal for each compressed time-series signal in the sub-group other than the respective base time-series signal, wherein the ratio determiner component generates the respective ratio signal based at least in part upon the respective base time-series signal, wherein the ratio determiner component generates an index that is employable to locate a particular compressed signal represented by a ratio signal in a sub-group, a time-series signal corresponding to the particular compressed signal being reconstructable based upon the ratio signal.

11. The system of claim 10, wherein the index comprises one of an array, a B-tree, or a hash table.

12. The system of claim 10, wherein the index comprise a multi skip list that facilitates retrieval of the particular compressed time-series signal over a specified time range.

13. The system of claim 10, wherein the grouper component generates the plurality of sub-groups through minimizing cost of a model of a general facility location problem.

14. The system of claim 10, wherein subsequent to generating the respective ratio signal for each compressed time-series signal in the sub-group, the ratio determiner component removes compressed time-series signals represented by ratio signals from the data repository.

15. The system of claim 10, wherein the plurality of components further comprise a query receiver component that receives a query, identifies a compressed time-series signal over which the query is to be executed, reconstructs the compressed time-series signal based at least in part upon the base signal and its respective ratio signal, and executes the query over the compressed time-series signal subsequent to the compressed time-series signal being reconstructed.

16. The system of claim 10, wherein the compressor component generates the plurality of compressed time-series signals from the respective plurality of time-series signals through utilization of constant piecewise linear approximation.

17. A computing apparatus comprising a computer-readable data storage device, the computer-readable data storage device comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

receiving a plurality of time-series signals from a data repository;

selecting, from the plurality of time-series signals, a base time-series signal;

computing measures of similarity between the base time-series signal and other respective time-series signals in the plurality of time-series signals;

generating a group of time-series signals based at least in part upon the measures of similarity, the group of time-series signals comprising the base time-series signal and at least one other time-series signal from the plurality of time-series signals;

generating a ratio signal that is representative of the at least one other time-series signal, the ratio signal being a division of the base time-series signal by the at least one other time-series signal, the ratio signal being a compression of the at least one other time-series signal;

generating a computer-readable index that maps the ratio signal to the at least one other time-series signal, the at least one other time-series signal being reconstructable based upon the ratio signal; and

subsequent to generating the ratio signal, removing the at least one other time-series signal from the data repository.