Computing Elementary Statistics: Time-Space Tradeoffs and Sliding Windows

Abstract:  We consider the complexity of computing element distinctness, frequency moments, and order statistics with limited space, as well as computing these statistics over "sliding windows" in a
single longer data sequence, a natural requirement for time-series data.

All of these elementary statistics can be easily computed for sorted inputs; however, as Borodin and Cook showed more than 30 years ago, sorting with small space requires nearly quadratic time.   Nearly tight time-space tradeoff lower bounds for comparison-based algorithms are known for these problems, including nearly quadratic lower bounds for element
distinctness and frequency moments, and it was conjectured that these bounds also hold for general algorithms.

We give a new algorithm for element distinctness that beats the comparison-based lower bound by roughly an (n/S)^{1/2} factor and show how this tradeoff can be extended to sliding windows.  A key component is an efficient generalization of Floyd's cycle-finding algorithm that can be applied for all space bounds. In contrast, we show that general algorithms for frequency moments do require quadratic tradeoffs over sliding windows.

We also give a tight time-space tradeoff lower bound for computing the median that generalizes lower bounds previously known only for comparison-based algorithms or for multi-pass data streams.

Joint work with Raphael Clifford, Widad Machmouchi, Vincent Liew, and Mihai Patrascu