Element Distinctness, Frequency Moments, and Sliding Windows

I will present new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics. These problems are simple to solve for sorted data. Determining the complexity of these problems where space is limited, on the other hand, requires considerably more effort. I will first discuss a new randomised algorithm for the element distinctness problem whose time and space complexity is roughly O(n^{3/2}/S^{1/2}), smaller than previous lower bounds for comparison-based algorithms. I will then show how to extend this method to a sliding window version with only log factor overheads. By way of contrast, I will then show tight (to within log factors) time-space tradeoff bounds for computing the number of distinct elements, F_0, over sliding windows. The same lower bound holds for computing the low-order bit of F_0 and computing any frequency moment F_k for k \ne 1. This shows that frequency moments F_k \ne 1 and even the decision problem F_0 \bmod 2 are strictly harder than element distinctness.

The paper is available online at http://arxiv.org/abs/1309.3690.

Joint work with Paul Beame and Widad Machmouchi.