Hierarchical sampling from sketches: Estimating functions over data streams

DOI10.1007/s00453-008-9260-5zbMath1166.68040OpenAlexW1997261473MaRDI QIDQ1016526

Sumit Ganguly, Lakshminath Bhuvanagiri

Publication date: 6 May 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.162.1697

zbMATH Keywords

entropydata streamsfrequency momentsHSS

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Randomized algorithms (68W20)

Related Items (2)

Taylor Polynomial Estimator for Estimating Frequency Moments ⋮ Estimating hybrid frequency moments of data streams

Cites Work

• An information statistics approach to data stream and communication complexity
• Probabilistic counting algorithms for data base applications
• New hash functions and their use in authentication and set equality
• Universal classes of hash functions
• The space complexity of approximating the frequency moments
• Estimating Entropy and Entropy Norm on Data Streams
• Space lower bounds for distance approximation in the data stream model
• Optimal approximations of the frequency moments of data streams
• Streaming and sublinear approximation of entropy and information distances
• An improved data stream summary: the count-min sketch and its applications
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Estimating Entropy over Data Streams
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hierarchical sampling from sketches: Estimating functions over data streams