Cell-probe bounds for online edit distance and other pattern matching problems

DOI10.1137/1.9781611973730.37zbMATH Open1371.68337arXiv1407.6559OpenAlexW2949935342MaRDI QIDQ5362986FDOQ5362986

Authors: Raphaël Clifford, Markus Jalsenius, Benjamin Sach 

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We give cell-probe bounds for the computation of edit distance, Hamming distance, convolution and longest common subsequence in a stream. In this model, a fixed string of $n$ symbols is given and one $delta$-bit symbol arrives at a time in a stream. After each symbol arrives, the distance between the fixed string and a suffix of most recent symbols of the stream is reported. The cell-probe model is perhaps the strongest model of computation for showing data structure lower bounds, subsuming in particular the popular word-RAM model. * We first give an $Omega((deltalogn)/(w+loglogn))$ lower bound for the time to give each output for both online Hamming distance and convolution, where $w$ is the word size. This bound relies on a new encoding scheme and for the first time holds even when $w$ is as small as a single bit. * We then consider the online edit distance and longest common subsequence problems in the bit-probe model ($w=1$) with a constant sized input alphabet. We give a lower bound of $Omega(sqrtlogn/(loglogn{)}^{3/2})$ which applies for both problems. This second set of results relies both on our new encoding scheme as well as a carefully constructed hard distribution. * Finally, for the online edit distance problem we show that there is an $O((logn{)}^2/w)$ upper bound in the cell-probe model. This bound gives a contrast to our new lower bound and also establishes an exponential gap between the known cell-probe and RAM model complexities.

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

Recommendations

• Cell-probe lower bounds for bit stream computation
• Tight Cell-Probe Bounds for Online Hamming Distance Computation
• Space Lower Bounds for Online Pattern Matching
• Space lower bounds for online pattern matching
• Time bounds for streaming problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Cited In (6)

• Space lower bounds for online pattern matching
• Time bounds for streaming problems
• Cell-probe lower bounds for bit stream computation
• Tight Cell-Probe Bounds for Online Hamming Distance Computation
• Space Lower Bounds for Online Pattern Matching
• Upper and lower bounds for dynamic data structures on strings

This page was built for publication: Cell-probe bounds for online edit distance and other pattern matching problems

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