An approximate L1-difference algorithm for massive data streams

We give a space-efficient, one-pass algorithm for approximating the L¹ difference Σ_i|a_i-b_i | between two functions, when the function values a_i and b_i are given as data streams, and their order is chosen by an adversary. Our main technical innovation is a method of constructing families {V_j} of limited independence random variables that are range summable by which we mean that Σ_j=0 ^c-1 V_j(s) is computable in time polylog(c), for all seeds s. These random variable families may be of interest outside our current application domain, i.e., massive data streams generated by communication networks. Our L¹-difference algorithm can be viewed as a “sketching” algorithm, in the sense of (A. Broder et al., 1998), and our algorithm performs better than that of Broder et al., when used to approximate the symmetric difference of two sets with small symmetric difference