Fast Grouping of Time Series

• US 20160140208A1
• Filed: 06/14/2013
• Published: 05/19/2016
• Est. Priority Date: 06/14/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Wang, Shulei, Dang, Yingnong, Wang, Qiang, Zhao, Qianchuan, Ding, Rui, Fu, Qiang, Zhang, Dongmei
• Granted Patent: US 10,176,246 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/90 Details of database functions independent of the retrieved data types
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06F 2218/16 by matching signal segments

Abstract

In some examples, a time-series data set can be analyzed and grouped in a fast and efficient manner. For instance, fast grouping of multiple time-series into clusters can be implemented through data reduction, determining cluster population, and fast matching by locality sensitive hashing. In some situations, a user can select a level of granularity for grouping time-series into clusters, which can involve trade-offs between the number of clusters and the maximum distance between two time-series in a cluster.

Claims

1. A method comprising:

collecting a plurality of time-series, wherein each of the plurality of time-series comprises a series of numerical values;

generating a plurality of feature vectors, wherein each of the plurality of feature vectors corresponds to one of the plurality of time-series;

mapping between granularity levels and distance thresholds for clustering, based, at least in part, on a subset of the plurality of feature vectors;

generating a plurality of seeds that corresponds to one of the granularity levels, based, at least in part, on the mapping; and

assigning each of the plurality of time-series to one of the plurality of seeds.

2. The method as recited in claim 1, wherein generating the plurality of feature vectors comprises:

determining a number for dividing each of the plurality of time-series;

dividing each of the plurality of time-series by the number to form a plurality of segments for each time-series, wherein each of the plurality of segments comprises an approximately equal number of numerical values; and

averaging numerical values within each segment of each of the plurality of segments.

3. The method as recited in claim 2, wherein determining the number for dividing each of the plurality of time-series comprises:

calculating a power spectrum of each of the plurality of time-series;

selecting a cut-off frequency such that for at least a first threshold percentage of the plurality of time-series, an energy of frequency components below the cut-off frequency is at least a second threshold percentage of an energy of the plurality of time-series; and

determining the number based, at least in part, on the cut-off frequency.

4. The method as recited in claim 3, wherein determining the number based, at least in part, on the cut-off frequency comprises multiplying the cutoff frequency by two.

5. The method as recited in claim 1, wherein generating a plurality of seeds that corresponds to one of the granularity levels, based, at least in part, on the mapping comprises:

transforming the subset of the plurality of feature vectors by encoding each numerical value of the plurality of feature vectors to a symbol based, at least in part, on a mapping of numerical values to symbols;

determining a distance threshold that corresponds to the one of the granularity levels based, at least in part, on the mapping; and

generating the plurality of seeds based, at least in part, on the distance threshold.

6. The method as recited in claim 1, wherein the one of the granularity levels is selected based, at least in part, on user input.

7. The method as recited in claim 1, wherein the subset of the plurality of feature vectors is randomly sampled from the plurality of feature vectors.

8. The method as recited in claim 1, wherein the assigning each of the plurality of time-series to one of the plurality of seeds is based, at least in part, on locality sensitive hashing.

9. A system comprising:

one or more processors;

a memory that includes a plurality of computer-executable components, the plurality of computer-executable components comprising a module to;

collect a plurality of time-series, wherein each of the plurality of time-series comprises a series of numerical values;

generate a plurality of feature vectors, wherein each of the plurality of feature vectors corresponds to one of the plurality of time-series;

generate a plurality of seeds that corresponds to a granularity level, based, at least in part, on at least a subset of the plurality of feature vectors; and

assigning each of the plurality of time-series to one of the plurality of seeds.

10. A computer-readable medium storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:

collecting a plurality of time-series that corresponds to a plurality of computing devices, wherein each of the plurality of time-series comprises a series of numerical values that represents resource consumption by a respective one of the computing devices during a time period;

generating a plurality of feature vectors based, at least in part, on a power spectrum of each of the plurality of time-series, wherein each of the plurality of feature vectors corresponds to a respective one of the plurality of time-series;

identifying clusters by applying density-based clustering to at least a portion of the plurality of feature vectors;

mapping between granularity levels and distance thresholds for each of a plurality of the clusters, based, at least in part, on a subset of the plurality of feature vectors;

generating a plurality of seeds that corresponds to one of the granularity levels based, at least in part, on the mapping, wherein the one of the granularity levels is selected based, at least in part, on user input;

assigning each of the plurality of time-series to one of the plurality of seeds based, at least in part, on hash values; and

presenting a graphic representation of at least one of the plurality of the clusters to indicate resource consumption of at least one of the computing devices during the time period.