3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ use a tree-based sorted collection in addition to your circular buffer. inserting into a sorted array is $O(n)$. $\endgroup$ – Solomonoff's Secret Aug 14 '18 at 17:29
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes mean and variance can be done without needing to store any samples at all (using Welford's algorithm). But for median say, if I had a sorted array I can find the median in O(1) time by simply accessing array[k/2] if k is odd. If the data is stored in an AVL tree, how could I quickly find the median element in the tree? $\endgroup$ – vibe Aug 14 '18 at 19:52
  • $\begingroup$ Also, a normal AVL tree has left/right pointers which will correspond to sorted entries. For my problem I would need additional pointers which correspond to the sequential order the samples come in the time series, so that I can delete the oldest sample from the tree. Is that what you mean by augmented AVL? $\endgroup$ – vibe Aug 14 '18 at 19:55
  • $\begingroup$ Keep pointer to median in the tree - this is part of augmentation. To maintain last / new element you need only to look it up in the tree when deleting. If this is unique, no additional work is done. If these are not unique, you have to keep multiplicity in nodes, but no additional data is needed. $\endgroup$ – Evil Aug 14 '18 at 20:41
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.