Hierarchical sampling from sketches: Estimating functions over data streams

DOI10.1007/S00453-008-9260-5MaRDI QIDQ1016526zbMATH OpenOpenAlexFDO

Authors 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) Randomized algorithms (68W20) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• On Estimating Frequency Moments of Data Streams
• Streaming algorithms via precision sampling
• Space-efficient estimation of statistics over sub-sampled streams
• Fast moment estimation in data streams in optimal space
• Estimating Entropy and Entropy Norm on Data Streams

Cites work

• scientific article; zbMATH DE number 2086663 (Why is no real title available?)
• A near-optimal algorithm for computing the entropy of a stream
• An improved data stream algorithm for frequency moments
• An improved data stream summary: the count-min sketch and its applications
• An information statistics approach to data stream and communication complexity
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Estimating Entropy and Entropy Norm on Data Streams
• Estimating Entropy over Data Streams
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• New hash functions and their use in authentication and set equality
• Optimal approximations of the frequency moments of data streams
• Optimal space lower bounds for all frequency moments
• Probabilistic counting algorithms for data base applications
• Space lower bounds for distance approximation in the data stream model
• Streaming and sublinear approximation of entropy and information distances
• Tabulation based 4-universal hashing with applications to second moment estimation
• The space complexity of approximating the frequency moments
• Universal classes of hash functions

Cited in

(2)

• Estimating hybrid frequency moments of data streams
• Taylor polynomial estimator for estimating frequency moments

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016526)