[Question / Feature Idea] Changing window size

[eddelbuettel]

This is a lovely little utility for streaming data. I have a somewhat related use case:

• my 'window' is time based,
• observations come as pairs with <t_i, x_i>
• your class helps for min(x_i) and max(x_i) for all i
• when adding I also check if the time span between newest and oldest exceeds 'window lengths'
• if so, pop old values

Is there are clever way to use your data structure to update?

[lemire]

As such, we don’t support this case, however clever algorithms are indeed possible. Whether they are relevant to your use case is difficult to tell in the abstract.

[eddelbuettel]

Point taken. I just looked at this for a somewhat trivial application (bounds / ranges for plots, I can afford to rescan and/or be appromimative) but I do have the more general problem of desiring approximate quantiles for streams ... and most of the work I have seen cannot be adapted easily of the case of 'fixed N time unit window seeing varying number M of points in that window' and efficient statistics. An interesting puzzle.

But thanks for the very prompt reply. If you have a relevant pointer I'd appreciate it. If not, no worries.

[lemire]

Ok. Well, we can discuss it.

Suppose you want percentile p for some value of p. Then you could could iteratively build two heaps, one containing values that are "large" and one that contains values that are "small". One heap is a min heap, one heap is a max heap. When a value comes in, you add it to one of the two heaps, and then you adjust the size of the heaps so that you get the right percentile.

Looks like this should be logarithmic time and it can be implemented using ten lines of code if you have a good heap implementation. It is going to be pretty fast... you could derive a tight bound on how many operations each step takes.

This works well if you only need on percentile value (e.g., the median).

If you need to track many percentiles....

Another practical approach might be to just throw the data points in a (sorted by value) tree. This way you have, at all times, access to the values in order. As the window moves, you need to add and remove values, but that's not too hard, you just need an auxiliary data structure (fifo-like). The tree balancing is likely to dominate, but you can probably do well with a b-tree implementation.

Everything I have discussed so far is, at best, logarithmic in the number of values you have in one window. I think that if you want to track an arbitrary number of percentiles, then this is genuinely the best you can hope for.

Tuning the tree-like implementation for performance might be interesting, but one would need a use case.

[eddelbuettel]

Thanks for that discussion, truly helpful at it has been decades since my last algorithms class and that Sedgewick copy is getting dusty too :) The mix/max heap for median is something I should try; a older SO answer has has pointers. Hopefully I'll find some time to work on this along with fifo-ness for updates.

As for tuning and the use cases: we have real-world (pricing) observations coming in, and we generally need things to be fast and predictable.

[lemire]

Anyhow, I am available and interested in collaborating.

[eddelbuettel]

Sorry for the long silence, I finally got some time to work on this and the STL_mono_wedge variant you kindly link to came in handy.

It took me longer than I care to admit in public to realize that I needed a structure like his struct sample { double val; double timeindex } in order to expunge old values -- I had not fully groked that container inside mono_wedge ends up having very different cardinality than the normal ringbuffer / vector / deque I used for the windowed data.

Now that this is taken care of maybe I can find time work on the mix+max heaps for a median.

[lemire]

+1