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
On Mon, Nov 19, 2012 at 9:02 PM, Leo Goodstadt <leo.goodstadt@llew.org.uk>wrote: 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