On Pruning of Data in a Sliding Window for Computing a Rank-Order Element

In a window of $\boldsymbol{N}$ elements, if $\boldsymbol{k}$ old elements are replaced by $\boldsymbol{k}$ new elements during a step, then $({\boldsymbol{N} - \boldsymbol{k}})$ old elements are still maintained in the new instance of the window. In this work, we show that not all such elements need to be maintained in the future instances of the sliding window for exact computation of a rank-order element. It is shown that depending on the value and the time order, an element of the current window may never become the intended rank-order element in any future instances of the window. Theoretical as well as simulation results show that significant reduction in the size of a window can be achieved by pruning or removing such elements or data samples from the window.