Space Lower Bounds for Online Pattern Matching

DOI10.1007/978-3-642-21458-5_17MaRDI QIDQ3011853zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Markus Jalsenius, Ely Porat, Benjamin Sach

Publication date 29 June 2011

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Abstract: We present space lower bounds for online pattern matching under a number of different distance measures. Given a pattern of length m and a text that arrives one character at a time, the online pattern matching problem is to report the distance between the pattern and a sliding window of the text as soon as the new character arrives. We require that the correct answer is given at each position with constant probability. We give Omega(m) bit space lower bounds for L_1, L_2, L_infty, Hamming, edit and swap distances as well as for any algorithm that computes the cross-correlation/convolution. We then show a dichotomy between distance functions that have wildcard-like properties and those that do not. In the former case which includes, as an example, pattern matching with character classes, we give Omega(m) bit space lower bounds. For other distance functions, we show that there exist space bounds of Omega(log m) and O(log^2 m) bits. Finally we discuss space lower bounds for non-binary inputs and show how in some cases they can be improved.

Recommendations

• Space lower bounds for online pattern matching
• scientific article; zbMATH DE number 7650307
• Online stochastic pattern matching
• Optimal On-Line Search and Sublinear Time Update in String Matching
• Pattern matching with non overlapping reversals -- approximation and on-line algorithms
• scientific article; zbMATH DE number 1740051
• On-line approximate string matching with bounded errors
• On-Line Approximate String Matching with Bounded Errors
• The exact online string matching problem: a review of the most recent results
• Cell-probe bounds for online edit distance and other pattern matching problems

Cites work

• Communication Complexity
• Exact and Approximate Pattern Matching in the Streaming Model
• Faster pattern matching with character classes using prime number encoding
• Maintaining Stream Statistics over Sliding Windows
• Pattern Matching with Swaps
• Private vs. common random bits in communication complexity
• String matching under a general matching relation
• The communication complexity of the Hamming distance problem
• The one-way communication complexity of Hamming distance
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(6)

• A Black Box for Online Approximate Pattern Matching
• Space lower bounds for online pattern matching
• Cell-probe lower bounds for bit stream computation
• Pattern matching in pseudo real-time
• Cell-probe bounds for online edit distance and other pattern matching problems
• A black box for online approximate pattern matching

This page was built for publication: Space Lower Bounds for Online Pattern Matching

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