Paper Info
Title
Element Distinctness, Frequency Moments, and Sliding Windows
Abstract
We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics, that are simple to calculate for sorted data. In particular, we develop a randomized algorithm for the element distinctness problem whose time T and space S satisfy T in O(n3/2/S1/2), smaller than previous lower bounds for comparison-based algorithms, showing that element distinctness is strictly easier than sorting for randomized branching programs. This algorithm is based on a new time- and space-efficient algorithm for finding all collisions of a function f from a finite set to itself that are reachable by iterating f from a given set of starting points. We further show that our element distinctness algorithm can be extended at only a polylogarithmic factor cost to solve the element distinctness problem over sliding windows, where the task is to take an input of length 2n-1 and produce an output for each window of length n, giving n outputs in total. In contrast, we show a time-space tradeoff lower bound of T in Omega(n2/S) for randomized multi-way branching programs, and hence standard RAM and word-RAM models, to compute 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 not equal 1. This shows that frequency moments F_k not equal 1 and even the decision problem F_0bmod 2 are strictly harder than element distinctness. We provide even stronger separations on average for inputs from [n]. We complement this lower bound with a T in O(n2/S) comparison-based deterministic RAM algorithm for exactly computing F_k over sliding windows, nearly matching both our general lower bound for the sliding-window version and the comparison-based lower bounds for a single instance of the problem. We also consider the computations of order statistics over sliding windows.
Year
DOI
Venue
2013
10.1109/FOCS.2013.39
foundations of computer science
Keywords
DocType
Volume
element distinctness algorithm,distinct element,comparison-based lower bound,element distinctness problem,previous lower bound,order statistic,sliding windows,frequency moments,element distinctness,lower bound,comparison-based algorithm,frequency moment,set theory,computational complexity,statistical analysis
Journal
abs/1309.3690
ISSN
Citations 
PageRank 
0272-5428
8
0.49
References 
Authors
26
3
Name
Order
Citations
PageRank
Paul Beame12234176.07
Raphaël Clifford226828.57
Widad Machmouchi3192.69