Maintaining a sorted moving window

Question

I have an array of length $n$ representing a time series of data. I want to implement a moving (sliding) window of length $k < n$ and calculate things like sliding median, sliding quantile, sliding trimmed mean, etc. Each of these requires the data to be sorted prior to calculating the statistic of interest.

Therefore I need a data structure which has the following 2 properties:

1. It must easily allow a new sample to be added and the oldest sample to be deleted as the window slides along the time series.

2. When a new sample is added, it should efficiently insert the sample into a sorted position in the data structure, so that things like the median and trimmed mean can easily be computed.

For #1, I am currently using a ring (circular) buffer of length $k$. This makes it easy to add new samples and overwrite old samples in $O(1)$ time simply by updating the head and tail pointers of the buffer.

For #2, I had thought to keep a separate array called perm to keep track of the permutation of the ring buffer entries needed to sort them. In other words, if array is the ring buffer array with head and tail pointers, then array[(head + perm[i]) % k] is the sorted array for i = 0,...,k-1. I tried using an Insertion Sort algorithm to update the perm array each time a new sample is added to the sliding window. The code for this is below.

/* sort ringbuf entries with insertion sort algorithm */
void
ringbuf_isort(const ringbuf *rbuf, int *perm)
{
  const int n = ringbuf_n(rbuf);
  int i, j;

  for (i = 1; i < n; i++)
    {
      int id = perm[i];
      double v = rbuf->array[(rbuf->head + id) % rbuf->size];

      for (j = i; j > 0; j--)
        {
          if (rbuf->array[(rbuf->head + perm[j-1]) % rbuf->size] < v)
            break;

          perm[j] = perm[j-1];
        }

      perm[j] = id;
    }
}

This code works correctly and sorts the ring buffer entires, however it is far too slow. I have tracked the slowdown to the modular arithmetic (rbuf->head + id) % rbuf->size in each loop iteration. This can be moderately improved by doing a comparison of id < head ? head + id : head + id - size, but this is still too slow.

In fact I have found it is faster to simply copy the ring buffer entries to a linear array and use a quicksort algorithm than using the above code.

Can anyone suggest a data structure which will solve the sorting problem and still be fast?

Answer 1

If you use augmented AVL (or any self-balancing tree like RB) tree with additional pointers for quantiles then maintaining median and quantiles work in logarithmic time. Inorder traversal is always sorted so if juggling with pointers is not good option for you, maintain tree, with one insert and delete per move and caclulated statistics during inorder traversal.

It is good to keep online algorithms whenever possible, keeping say mean or variance as accumulators, not recalculating all the time.

I have similar need, only maintaining median, mean, standard deviation and kurtosis. Here I keep threaded AVL tree with additional online version of statistics, moving median pointer on insert/delete.

Answer 2

Store the last $k$ elements twice: once in a circular buffer (in the order they appear), and once in a sorted set (in increasing order). The circular buffer is easy to update in $O(1)$ time. The sorted set can be updated in $O(\log n)$ time if you use a self-balancing binary tree (e.g., AVL tree, red-black tree, etc.).

Each time an element arrives, you first delete the oldest item (look it up in the circular buffer, remove it from the sorted set), then add the newest item (add it to the circular buffer, add it to the sorted set). Now you can compute the median, quantiles, etc., of the last $k$ items directly from the sorted set in $O(\log n)$ time.

For the mean and variance, you do something different. The mean is easy if you maintain a running sum of the last $k$ items (so when a new item arrives, you subtract off the oldest value and add the newest value). The standard deviation or variance requires a bit more work to do to compute in a numerically stable way. Look up streaming/online algorithms for the mean and variance (e.g., https://dsp.stackexchange.com/q/811/5874, https://math.stackexchange.com/questions/20593/calculate-variance-from-a-stream-of-sample-values, https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance).