Counting Distinct Elements in a Data Stream

Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar and Luca Trevisan

View Related Documents

Journal Article
Time-Space Tradeoff in Derandomizing Probabilistic Logspace
Jin-Yi Cai, Venkatesan T. Chakaravarthy and Dieter van Melkebeek
Theory of Computing Systems, 2006, Volume 39, Number 1, Pages 189-208
- Download PDF (327.3 KB)
Book Chapter
Broadword Computing and Fibonacci Code Speed Up Compressed Suffix Arrays
Simon Gog
Lecture Notes in Computer Science, 2009, Volume 5526, Experimental Algorithms, Pages 161-172
- Download PDF (277.0 KB)
Book Chapter
Hardware and software synthesis, optimization, and verification from Esterel programs
Gérard Berry
Lecture Notes in Computer Science, 1997, Volume 1217, Tools and Algorithms for the Construction and Analysis of Systems, Pages 1-3
- Download PDF (156.8 KB)
Book Chapter
Pebbling and Proofs of Work
Cynthia Dwork, Moni Naor and Hoeteck Wee
Lecture Notes in Computer Science, 2005, Volume 3621, Advances in Cryptology – CRYPTO 2005, Pages 37-54
- Download PDF (248.2 KB)
Book Chapter
On the difficulty of range searching
Arne Andersson and Kurt Swanson
Lecture Notes in Computer Science, 1995, Volume 955, Algorithms and Data Structures, Pages 473-481
- Download PDF (566.0 KB)
Book Chapter
Self-Organizing Hierarchical Cluster Timestamps
Paul A. S. Ward and David J. Taylor
Lecture Notes in Computer Science, 2001, Volume 2150, Euro-Par 2001 Parallel Processing, Pages 46-56
- Download PDF (168.1 KB)
Book Chapter
Aggregate Computation over Data Streams
Xuemin Lin and Ying Zhang
Lecture Notes in Computer Science, 2008, Volume 4976, Progress in WWW Research and Development, Pages 10-25
- Download PDF (467.9 KB)
Book Chapter
Finding Many Optimal Paths Without Growing Any Optimal Path Trees
Danny Z. Chen and Ewa Misiołek
Lecture Notes in Computer Science, 2007, Volume 4598, Computing and Combinatorics, Pages 232-242
- Download PDF (472.1 KB)
Book Chapter
Computing Inverse ST in Linear Complexity
Ge Nong, Sen Zhang and Wai Hong Chan
Lecture Notes in Computer Science, 2008, Volume 5029, Combinatorial Pattern Matching, Pages 178-190
- Download PDF (421.1 KB)
Journal Article
New Results on Path Approximation
Ovidiu Daescu
Algorithmica, 2004, Volume 38, Number 1, Pages 131-143
- Download PDF (196.1 KB)
- View HTML

Abstract

We present three algorithms to count the number of distinct elements in a data stream to within a factor of 1 ±ε. Our algorithms improve upon known algorithms for this problem, and offer a spectrum of time/space tradeoffs.

Part of this work was done while the author was visiting IBM Almaden Research Center. Supported by NSF Grant CCR-9820897.

Work supported by a Sloan Research Fellowship and an NSF Career Award.

Fulltext Preview

Image of the first page of the fulltext document

Frequently asked questions General info on journals and books Send us your feedback Impressum Contact us

SpringerLink

Counting Distinct Elements in a Data Stream

View Related Documents

Abstract

Fulltext Preview