Data Stream Algorithms via Expander Graphs

DOI10.1007/978-3-540-92182-0_8MaRDI QIDQ3596706zbMATH OpenOpenAlexFDO

Authors Sumit Ganguly

Publication date 29 January 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92182-0_8

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Optimal approximations of the frequency moments of data streams
• An improved data stream algorithm for frequency moments
• scientific article; zbMATH DE number 2019620
• scientific article; zbMATH DE number 1424324
• Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)

Cited in

(4)

• Dynamic graph stream algorithms in \(o(n)\) space
• Efficiently decodable error-correcting list disjunct matrices and applications (extended abstract)
• Extended dynamic partial-overlapping batch means estimators for steady-state simulations
• On low-risk heavy hitters and sparse recovery schemes

This page was built for publication: Data Stream Algorithms via Expander Graphs

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