Periodicity and cyclic shifts via linear sketches

DOI10.1007/978-3-642-22935-0_14MaRDI QIDQ3088091zbMATH OpenOpenAlexFDO

Authors Michael S. Crouch, Andrew McGregor

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) Algorithms on strings (68W32) Sampling theory in information and communication theory (94A20)

Recommendations

• Periodicity in streams
• Periodicity testing with sublinear samples and space
• LATIN 2004: Theoretical Informatics
• Streaming periodicity with mismatches
• On Estimating Frequency Moments of Data Streams

Cites work

• scientific article; zbMATH DE number 1615297 (Why is no real title available?)
• scientific article; zbMATH DE number 3141365 (Why is no real title available?)
• scientific article; zbMATH DE number 5764818 (Why is no real title available?)
• 1-pass relative-error \(L_p\)-sampling with applications
• An improved data stream summary: the count-min sketch and its applications
• Data Streams: Algorithms and Applications
• Exact and Approximate Pattern Matching in the Streaming Model
• Near-optimal sparse fourier representations via sampling
• On the exact space complexity of sketching and streaming small norms
• Periodicity in streams
• Periodicity testing with sublinear samples and space
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Pseudorandom generators for space-bounded computation
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• The space complexity of approximating the frequency moments

Cited in

(6)

• Dictionary matching in a stream
• Periodicity testing with sublinear samples and space
• Periodicity in streams
• On approximating matrix norms in data streams
• scientific article; zbMATH DE number 7758348 (Why is no real title available?)
• Streaming periodicity with mismatches

This page was built for publication: Periodicity and cyclic shifts via linear sketches

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