Sampling in Sliding Windows with Tight Optimality and Time Decayed Design

摘要

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 t_span and uses a backward probability decay curve to specify what priority values are included in the sliding window. This defines, for a current time t_c, a current data sample consisting of data items whose timestamps t fall within the time span t_c−t_span≤t≤t_c and 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.