PREDICTION FOR TIME SERIES DATA USING A SPACE PARTITIONING DATA STRUCTURE

摘要

Techniques are disclosed for a computer system to predict a next sample for a data stream that specifies data values of one or more variables. A current subset of data values and previous subsets of data values is determined, and polyline simplification techniques may then be used on the subset to produce a reduced-sample current subset of data values that are converted to an angular coordinate system. A space partitioning data structure such as a k-dimensional tree that stores converted reduced-sample previous subsets of the data stream may then be traversed to determine one or more nearest neighbors to the current subset. The predicted next sample for the data stream may be generated from the nearest neighbors. The space partitioning data structure may be updated to include the current subset, and the process may be repeated with a new current subset.