Periodicity and Cyclic Shifts via Linear Sketches

DOI10.1007/978-3-642-22935-0_14zbMath1343.68193OpenAlexW1673624119MaRDI QIDQ3088091

Andrew McGregor, Michael S. Crouch

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_14

Mathematics Subject Classification ID

Time series, auto-correlation, regression, etc. in statistics (GARCH) (62M10) Learning and adaptive systems in artificial intelligence (68T05) Sampling theory in information and communication theory (94A20) Algorithms on strings (68W32)

Related Items (5)

Dictionary Matching in a Stream ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Periodicity in data streams with wildcards ⋮ On Approximating Matrix Norms in Data Streams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudorandom generators for space-bounded computation
• The space complexity of approximating the frequency moments
• Periodicity testing with sublinear samples and space
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Data Streams: Algorithms and Applications
• Near-optimal sparse fourier representations via sampling
• Periodicity in Streams
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• An improved data stream summary: the count-min sketch and its applications
• Exact and Approximate Pattern Matching in the Streaming Model

This page was built for publication: Periodicity and Cyclic Shifts via Linear Sketches