## Abstract

We give a space-efficient, one-pass algorithm for approximating the L^{1} 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^{1}-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 - Dec 1 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