Approximate L1-difference algorithm for massive data streams

J. Feigenbaum, S. Kannan, M. Strauss, M. Viswanathan

Research output: Contribution to journalConference article

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 languageEnglish (US)
Pages (from-to)501-511
Number of pages11
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1999
Externally publishedYes
EventProceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA
Duration: Oct 17 1999Oct 19 1999

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Approximate L<sup>1</sup>-difference algorithm for massive data streams'. Together they form a unique fingerprint.

  • Cite this