Re: [boost] Countertree

Subject: Re: [boost] Countertree
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2012-11-19 14:42:34

On Mon, Nov 19, 2012 at 9:02 PM, Leo Goodstadt <leo.goodstadt_at_[hidden]>wrote:

> 1) For counter trees, the median is just the N/2-th value in the
> counter tree, where K is the size of the tree.
> The Nth-percentile can be calculated similarly.
> A rolling median with a fixed size window requires there to be an
> insertion and deletion for each (most!) new value, so I am guessing
> it should run in O(N log K) time, where N =  size of data, K = size of
> window
>
> IIUC, it is better to avoid modifying original data (size N), the rolling
window of size K can be represented by a multiset based on an augmented
tree. This method guarantees complexity of obtaining 1st median value for
O(K log K) operations, which is the cost of construction of the rolling
window, every subsequent median value can be obtained for O(log K)
operations, when the window rolls. This approach should be more efficient.

Regards,
Vadim Stadnik