Time lower bounds for nonadaptive turnstile streaming algorithms

DOI10.1145/2746539.2746542MaRDI QIDQ2941576zbMATH OpenOpenAlexFDO

Authors

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.2151

zbMATH Keywords

cell probe modelheavy hitterspoint querystreamingtime lower bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Randomized algorithms (68W20)

Abstract: We say a turnstile streaming algorithm is "non-adaptive" if, during updates, the memory cells written and read depend only on the index being updated and random coins tossed at the beginning of the stream (and not on the memory contents of the algorithm). Memory cells read during queries may be decided upon adaptively. All known turnstile streaming algorithms in the literature are non-adaptive. We prove the first non-trivial update time lower bounds for both randomized and deterministic turnstile streaming algorithms, which hold when the algorithms are non-adaptive. While there has been abundant success in proving space lower bounds, there have been no non-trivial update time lower bounds in the turnstile model. Our lower bounds hold against classically studied problems such as heavy hitters, point query, entropy estimation, and moment estimation. In some cases of deterministic algorithms, our lower bounds nearly match known upper bounds.

Recommendations

• Turnstile streaming algorithms might as well be linear sketches
• scientific article; zbMATH DE number 6789285
• Deterministic heavy hitters with sublinear query time
• Fast moment estimation in data streams in optimal space
• Efficient sampling of non-strict turnstile data streams

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(6)

• Faster Update Time for Turnstile Streaming Algorithms
• Turnstile streaming algorithms might as well be linear sketches
• Tracking the l₂ Norm with Constant Update Time
• Space limited linear-time graph algorithms on big data
• Nearly time-optimal kernelization algorithms for the line-cover problem with big data
• From tcs to learning theory (invited paper)

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Time lower bounds for nonadaptive turnstile streaming algorithms

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