Method and apparatus for detecting a change-point in a time-series of computer telemetry signals

• US 20070239740A1
• Filed: 04/11/2006
• Published: 10/11/2007
• Est. Priority Date: 04/11/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Thampy, Sajjit, Gross, Kenny
• Granted Patent: US 7,542,995 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06F 2218/12 Classification; Matching

Abstract

A system that detects a change point in a time series of telemetry signals from a computer system. During operation, the system receives the time series of telemetry signals from the computer system. For each element in the time series, the system (1) inserts the element into a data structure which keeps track of the number of elements in the data structure that have a value greater than and that have a value less than the value of the inserted element; and (2) uses the information stored in the data structure to add a contribution by the inserted element to a trend statistic for the time series. The system then uses the trend statistic to select a hypothesis for the trend in the time series.

Claims

1. A method for detecting a change-point in a time-series of telemetry signals from a computer system, comprising:

receiving the time-series of telemetry signals from the computer system;

for each element in the time-series,

inserting the element into a data structure which keeps track of the number of elements in the data structure that have a value greater than and that have a value less than the value of the inserted element; and

using the information stored in the data structure to add a contribution by the inserted element to a trend statistic for the time-series; and

using the trend statistic to select a hypothesis for the trend in the time-series.

2. The method of claim 1, wherein the telemetry signals can include hardware variables and/or software variables.

3. The method of claim 2, wherein the software variables include load metrics, CPU utilization, idle time, memory utilization, disk activity, transaction latencies, and other performance metrics reported by the operating system.

4. The method of claim 2, wherein the hardware variables include temperature, voltage, current, fan speeds, accelerometer signals, acoustic signals, relative humidity, and signals from other physical transducers.

5. The method of claim 1, further comprising:

computing a confidence factor based on the trend statistic and the number of elements in the time-series;

if the confidence factor is below a specified confidence level, rejecting the hypothesis; and

otherwise, accepting the hypothesis.

6. The method of claim 1,

wherein the data structure is a substantially-balanced binary search tree;

and

wherein inserting the element into the data structure involves;

determining the value of the element;

traversing the substantially-balanced binary search tree until a leaf-node is reached, wherein at each node of the substantially balanced binary search tree, the value of the element being inserted is compared to the value of the element stored at the node to determine which sub-tree of the node to follow;

creating a new node at the leaf-node;

inserting the element at the new node; and

for each node,

updating a variable at the node which indicates the number of elements in the substantially balanced binary search tree that have a value less than the value of the element stored at the node; and

updating a variable at the node which indicates the number of elements in the substantially balanced binary search tree that have a value greater than the value of the element stored at the node.

7. The method of claim 6, wherein traversing the substantially-balanced binary search tree until a leaf-node is reached involves:

if the value of the element being inserted is less than the value of the element stored at the node, selecting the sub-tree which corresponds to values less than the value stored at the node; and

if the value of the element being inserted is greater than the value of the element stored at the node, selecting the sub-tree which corresponds to values greater than the value stored at the node.

8. The method of claim 6,

wherein the substantially balanced binary search tree is an AVL-tree, and

wherein for each node of the AVL-tree, the heights of the left sub-tree and the right sub-tree differ by at most one.

9. The method of claim 1, wherein using the information stored in the data structure to add the contribution by the inserted element to the trend statistic for the time-series involves:

computing the contribution by the inserted element to the trend statistic by taking the difference between the number of elements in the data structure that have a value greater than the value of the inserted element and the number of elements in the data structure than have a value less than the value of the inserted element; and

adding the contribution by the inserted element to the trend statistic for the time-series.

10. The method of claim 1, wherein using the trend statistic to select a hypothesis for the trend in the time-series involves:

determining if the trend statistic for the time-series indicates that the trend in the time-series is increasing;

if so, selecting an increasing-trend hypothesis;

otherwise, determining if the trend statistic for the time-series indicates that the trend in the time-series is decreasing;

if so, selecting a decreasing-trend hypothesis;

otherwise, selecting the null hypothesis.

11. The method of claim 1, wherein prior to inserting elements into the data structure, the method further comprises removing duplicate values from the time-series.

12. The method of claim 11, wherein after using the information stored in the data structure to add the contribution by the inserted element to a trend statistic for the time-series, the method further comprises inserting duplicate values back into the data structure.

13. The method of claim 1, wherein elements in the time-series are inserted into the data structure in reverse-chronological order.

14. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for detecting a change-point in a time-series of telemetry signals from a computer system, comprising:

receiving the time-series of telemetry signals from the computer system;

for each element in the time-series,

inserting the element into a data structure which keeps track of the number of elements in the data structure that have a value greater than and that have a value less than the value of the inserted element; and

using the information stored in the data structure to add a contribution by the inserted element to a trend statistic for the time-series; and

using the trend statistic to select a hypothesis for the trend in the time-series.

15. The computer-readable storage medium of claim 14, wherein the telemetry signals can include hardware variables and/or software variables.

16. The computer-readable storage medium of claim 15, wherein the software variables include load metrics, CPU utilization, idle time, memory utilization, disk activity, transaction latencies, and other performance metrics reported by the operating system.

17. The computer-readable storage medium of claim 15, wherein the hardware variables include temperature, voltage, current, fan speeds, accelerometer signals, acoustic signals, relative humidity, and signals from other physical transducers.

18. The computer-readable storage medium of claim 14, the method further comprising:

computing a confidence factor based on the trend statistic and the number of elements in the time-series;

if the confidence factor is below a specified confidence level, rejecting the hypothesis; and

otherwise, accepting the hypothesis.

19. The computer-readable storage medium of claim 14,

wherein the data structure is a substantially-balanced binary search tree;

and

wherein inserting the element into the data structure involves;

determining the value of the element;

traversing the substantially-balanced binary search tree until a leaf-node is reached, wherein at each node of the substantially balanced binary search tree, the value of the element being inserted is compared to the value of the element stored at the node to determine which sub-tree of the node to follow;

creating a new node at the leaf-node;

inserting the element at the new node; and

for each node,

updating a variable at the node which indicates the number of elements in the substantially balanced binary search tree that have a value less than the value of the element stored at the node; and

updating a variable at the node which indicates the number of elements in the substantially balanced binary search tree that have a value greater than the value of the element stored at the node.

20. The computer-readable storage medium of claim 19, wherein traversing the substantially-balanced binary search tree until a leaf-node is reached involves:

if the value of the element being inserted is less than the value of the element stored at the node, selecting the sub-tree which corresponds to values less than the value stored at the node; and

if the value of the element being inserted is greater than the value of the element stored at the node, selecting the sub-tree which corresponds to values greater than the value stored at the node.

21. The computer-readable storage medium of claim 19,

wherein the substantially balanced binary search tree is an AVL-tree, and

wherein for each node of the AVL-tree, the heights of the left sub-tree and the right sub-tree differ by at most one.

22. The computer-readable storage medium of claim 14, wherein using the information stored in the data structure to add the contribution by the inserted element to the trend statistic for the time-series involves:

computing the contribution by the inserted element to the trend statistic by taking the difference between the number of elements in the data structure that have a value greater than the value of the inserted element and the number of elements in the data structure than have a value less than the value of the inserted element; and

adding the contribution by the inserted element to the trend statistic for the time-series.

23. The computer-readable storage medium of claim 14, wherein using the trend statistic to select a hypothesis for the trend in the time-series involves:

determining if the trend statistic for the time-series indicates that the trend in the time-series is increasing;

if so, selecting an increasing-trend hypothesis;

otherwise, determining if the trend statistic for the time-series indicates that the trend in the time-series is decreasing;

if so, selecting a decreasing-trend hypothesis;

otherwise, selecting the null hypothesis.

24. The computer-readable storage medium of claim 14, wherein prior to inserting elements into the data structure, the method further comprises removing duplicate values from the time-series.

25. The computer-readable storage medium of claim 24, wherein after using the information stored in the data structure to add the contribution by the inserted element to a trend statistic for the time-series, the method further comprises inserting duplicate values back into the data structure.

26. The computer-readable storage medium of claim 14, wherein elements in the time-series are inserted into the data structure in reverse-chronological order.

27. An apparatus that detects a change-point in a time-series of telemetry signals from a computer system, comprising:

a receiving mechanism configured to receive the time-series of telemetry signals from the computer system;

a change-point-detection mechanism configured to;

for each element in the time-series, to

insert the element into a data structure which keeps track of the number of elements in the data structure that have a value greater than and that have a value less than the value of the inserted element; and

to

use the information stored in the data structure to add a contribution by the inserted element to a trend statistic for the time-series; and

to

use the trend statistic to select a hypothesis for the trend in the time-series.