Counting distinct items over update streams

DOI10.1016/j.tcs.2007.02.031zbMath1120.68115OpenAlexW2089066317MaRDI QIDQ2371800

Sumit Ganguly

Publication date: 9 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.031

zbMATH Keywords

randomized algorithmonline algorithmdata streamnegative dependencedistinct items

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Randomized algorithms (68W20)

Related Items (5)

Secure sampling with sublinear communication ⋮ Unnamed Item ⋮ Facility Location in Dynamic Geometric Data Streams ⋮ Unnamed Item ⋮ Efficient sampling of non-strict turnstile data streams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic counting algorithms for data base applications
• New hash functions and their use in authentication and set equality
• Pseudorandom generators for space-bounded computation
• The space complexity of approximating the frequency moments
• Min-wise independent permutations
• Optimal approximations of the frequency moments of data streams
• Balls and bins: A study in negative dependence

This page was built for publication: Counting distinct items over update streams