Non-parametric change point detection

• US 9,692,674 B1
• Filed: 12/30/2013
• Issued: 06/27/2017
• Est. Priority Date: 12/30/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lawlor, Matthew, Zhang, Xinyi, Yu, Kevin
• Primary Examiner(s): Joo, Joshua
• Application Number:
  US14/144,099
• Time in Patent Office: 1,275 Days
• Field of Search: None
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level

Abstract

Described herein are systems, mediums, and methods for simultaneously determining multiple types of changes in time series data. A plurality of potential change points may be selected in a signal representing the time series data. For each potential change point the signal may be a split into two segments including data points before and data points after the potential change point, respectively. Estimate of cumulative distribution function for each segment may be determined. A normalized difference of the respective estimates of cumulative distribution functions may be determined. The normalized difference may be compared to a threshold value to determine whether the potential change point qualifies as valid change point. The techniques discussed herein may determine at least two valid change points representing at least two different types of changes in the signal.

Claims

1. A computer-implemented method for determining change points in network traffic data based on evaluating time-series data associated with the network traffic data, the method comprising:

receiving, by a computing device over a network connection, a signal that identifies magnitudes of the network traffic data on a network over time;

selecting, using the computing device, a first potential change point in the signal;

identifying, using the computing device, a first portion of the signal incorporating data points before the first potential change point;

determining, using the computing device, a first cumulative distribution function estimate for the first portion of the signal;

identifying, using the computing device, a second portion of the signal incorporating data points after the first potential change point;

determining, using the computing device, a second cumulative distribution function estimate for the second portion of the signal;

determining, using the computing device, a normalized difference of the first and second cumulative distribution function estimates of the respective first and second portions of the signal; and

determining, using the computing device, whether the first potential change point qualifies as a valid data traffic magnitude change point based on the normalized difference.

2. The method of claim 1, further comprising:

comparing the normalized difference to a threshold value; and

determining whether the potential change point qualifies as a valid data traffic magnitude change point based on the comparing.

3. The method of claim 1, further comprising:

approximating the signal by a sequence of independent random variables prior to selecting the first potential change point.

4. The method of claim 1, further comprising:

prior to selecting the first potential change point;

determining a trend, a correlation or a cyclic pattern in the signal; and

removing the determined trend, the correlation or the cyclic pattern from the signal.

5. The method of claim 1, wherein the signal is processed online.

6. The method of claim 1, wherein the signal is saved to memory and processed offline.

7. The method of claim 1, wherein it is determined that the first potential change point qualifies as a valid data traffic magnitude change point based on the normalized difference, the method further comprising:

processing the signal to select a second potential change point in the signal;

identifying a third portion of the signal incorporating data points before the second potential change point;

determining a third cumulative distribution function estimate for the third portion of the signal;

identifying a fourth portion of the signal incorporating data points after the second potential change point;

determining a fourth cumulative distribution function estimate for the fourth portion of the signal;

determining a normalized difference of the third cumulative distribution function estimate and the fourth cumulative distribution function estimate of the respective third and fourth portions of the signal; and

determining that the second potential change point qualifies as a valid data traffic magnitude change point based on the normalized difference of the third cumulative distribution function estimate and the fourth cumulative distribution function estimate, wherein the second potential change point represents a change in the signal that is of a different type than a change represented by the first potential change point.

8. A non-transitory electronic device readable storage medium storing instructions to determine change points in network traffic data based on evaluating time-series data associated with the network traffic data that, when executed, cause one or more processors to:

receiving over a network connection a signal that identifies magnitudes of the network traffic data on a network over time;

select a plurality of potential change points in the signal, for each potential change point of the plurality of potential change points;

identify a first portion of the signal incorporating data points before the potential change point;

determine a first cumulative distribution function estimate for the first portion of the signal;

identify a second portion of the signal incorporating data points after the potential change point;

determine a second cumulative distribution function estimate for the second portion of the signal;

determine a normalized difference of the first cumulative distribution function estimate and the second cumulative distribution function estimate;

determine whether the potential change point qualifies as a valid data traffic magnitude change point based on the normalized difference; and

determine at least two valid data traffic magnitude change points in the signal based on normalized differences determined for the plurality of potential change points, wherein the at least two valid data traffic magnitude change points represents at least two types of changes in the signal.

9. The medium of claim 8, further storing instructions that, when executed, cause one or more processors to:

for each potential change point of the plurality of potential change points;

compare the normalized difference to a threshold value, and

determine whether the potential change point qualifies as a valid data traffic magnitude change point based on the comparing.

10. The medium of claim 8, further storing instructions that, when executed, cause one or more processors to:

approximate the signal by a sequence of independent random variables prior to processing the signal.

11. The medium of claim 8, wherein the signal is processed online.

12. The medium of claim 8, wherein the signal is saved to memory and processed offline.