Discarding data points in a time series

Abstract

Described herein are techniques for determining which data points in a time series to discard. A time series may include multiple data points. Spaced intervals over the time series may be determined. The data points can be ranked at least in part based on their respective distance from a nearest spaced interval. A data point may be discarded based on the ranking.

What is claimed is: 
     
         1 . A method comprising, by a processing system:
 receiving a stream of time series data comprising multiple data points; and   while receiving the stream:   (1) storing each received data point until a limit is reached; and   (2) upon receiving each additional data point, performing a retention process as follows:
 (a) retaining the first data point and the last data point; 
 (b) determining spaced intervals over the time series between the first and last data points; 
 (c) ranking each remaining data point, a data point's rank being based at least in part on the data point's distance from the data point's nearest spaced interval; and 
 (d) discarding a data point based on its ranking. 
   
     
     
         2 . The method of  claim 1 , further comprising:
 determining whether a data point has a characteristic, the data point's rank being based at least in part on whether the data point has the characteristic.   
     
     
         3 . The method of  claim 2 , wherein the characteristic comprises one of being a maximum value in the time series, being a minimum value in the time series, and being an inflexion point in the time series. 
     
     
         4 . The method of  claim 2 , wherein it is determined whether he data point has the characteristic by applying a function to the data point. 
     
     
         5 . The method of  claim 2 , wherein it is determined whether the data point has any of multiple characteristics, each characteristic having an effect on the data point's ranking. 
     
     
         6 . The method of  claim 2 , wherein the time series data is multivariate such that each data point comprises measurements for multiple metrics at a particular time, the data point's rank being based at least in part on whether any metric measurement of the data point has the characteristic. 
     
     
         7 . The method of  claim 2 , wherein it is determined whether the data point has the characteristic at any of multiple levels of execution. 
     
     
         8 . The method of  claim 7 , wherein the stream of time series data is received from a query engine, the time series data representing measurements of a metric related to execution of a query. 
     
     
         9 . The method of  claim 8 , wherein the multiple levels of execution comprise at least two of a query level, a query phase level, a node level, a path level, and an operator level. 
     
     
         10 . The method of  claim 1 , the retention process further comprising retaining the remaining data points. 
     
     
         11 . The method of  claim 1 , wherein the spaced intervals are substantially equal spaced time intervals from the first data point in the time series to the last data point in the time series. 
     
     
         12 . The method of  claim 1 , wherein the limit is a storage allocation limit. 
     
     
         13 . The method of  claim 1 , wherein the data point farthest from its nearest spaced interval is assigned the highest rank. 
     
     
         14 . A system comprising:
 a database to store data points in a multivariate time series, the data points comprising measurements of metrics collected by a query execution engine during execution of a query;   a retention engine to determine which measurements to retain upon reaching a limit, the retention engine configured to perform a retention process upon receiving a new data point, the retention process comprising:   (a) retaining a first data point and a last data point;   (b) determining spaced intervals over the time series;   (c) ranking each remaining data point using a ranking function, the ranking function being configured to assign a rank to a data point based at least in part on the data point's distance from its nearest spaced interval;   (d) discarding the highest ranked data point; and   (e) retaining the remaining data points.   
     
     
         15 . The system of  claim 14 , wherein the retention engine further configured to:
 determine whether a data point has a characteristic, the ranking function being configured to assign a rank to a data point based at least in part on whether the data point has the characteristic.   
     
     
         16 . The system of  claim 14 , further comprising:
 an aggregator to aggregate the measurements of the metrics at multiple levels of execution of the query,   wherein the retention engine is further configured to determine whether a data point has the characteristic at any of multiple levels, the multiple levels comprising at least two of a query level, a query phase level, a node level, a path level, and an operator level.   
     
     
         17 . A non-transitory computer-readable storage medium storing instructions for execution by a computer, the instructions when executed causing the computer to:
 store multiple data points from a stream of time series data; and   upon receiving an additional data point from the stream:   (a) determine spaced intervals over the time series;   (b) rank data points based at least in part on their respective distance from their respective nearest spaced interval; and   (c) discard the highest ranked data point.