Sampling in sliding windows with tight optimality and time decayed design

Abstract

A method samples a stream of data items. Each data item has an associated timestamp. The method assigns a priority value to each data item. Each data item is represented as a point on a two-dimensional graph whose axes are time and priority. A sliding window covers a predetermined length of time tand uses a backward probability decay curve to specify what priority values are included in the sliding window. This defines, for a current time t, a current data sample consisting of data items whose timestamps t fall within the time span t−t≤t≤tand have priority values below the decay curve. The data sample is stored in a buffer. The process iteratively moves the sliding window forward by a time increment, creating a provisional data sample. When the size of the provisional data sample is too large or too small, the process scales the decay curve.