Abstract
We give a space-efficient, one-pass algorithm for approximating the L1 difference Σi|ai - bi| between two functions, when the function values ai and bi are given as data streams, and their order is chosen by an adversary. Our main technical innovation is a method of constructing families {Vj} of limited-independence random variables that are range-summable, by which we mean that Σj=0c-1Vj(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 L1-difference algorithm can be viewed as a 'sketching' algorithm, in the sense of [Border, Charikar, Frieze, and Mitzenmacher, STOC '98, pp. 327-336], 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.
Original language | English (US) |
---|---|
Pages (from-to) | 501-511 |
Number of pages | 11 |
Journal | Annual Symposium on Foundations of Computer Science - Proceedings |
State | Published - 1999 |
Externally published | Yes |
Event | Proceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA Duration: Oct 17 1999 → Oct 19 1999 |
ASJC Scopus subject areas
- Hardware and Architecture