Optimal Streaming and Tracking Distinct Elements with High Probability
Abstract
The distinct elements problem is one of the fundamental problems in streaming algorithms—given a stream of integers in the range { 1,… , n }, we wish to provide a (1+ε) approximation to the number of distinct elements in the input. After a long line of research an optimal solution for this problem with constant probability of success, using O (1/ε 2 +lg n ) bits of space, was given by Kane, Nelson, and Woodruff in 2010.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 05, 2019
- Source ID
- 10.1145/3309193
Entities
People
- Jarosław Błasiok
Organizations
- Harvard University
- Office of Naval Research