Abstract
We give cellprobe 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 cellprobe model is perhaps the strongest model of computation for showing data structure lower bounds, subsuming in particular the popular wordRAM model. * We first give an $\Omega((\delta \log n)/(w+\log\log n))$ 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 bitprobe model ($w=1$) with a constant sized input alphabet. We give a lower bound of $\Omega(\sqrt{\log n}/(\log\log n)^{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((\log n)^2/w)$ upper bound in the cellprobe model. This bound gives a contrast to our new lower bound and also establishes an exponential gap between the known cellprobe and RAM model complexities.
Original language  English 

Title of host publication  ACMSIAM Symposium on Discrete Algorithms 
Publication status  Published  4 Jan 2015 
Event  ACMSIAM Symposium on Discrete Algorithms (2015)  San Diego, United States Duration: 4 Jan 2015 → 6 Jan 2015 Conference number: 26 
Conference
Conference  ACMSIAM Symposium on Discrete Algorithms (2015) 

Abbreviated title  SODA15 
Country/Territory  United States 
City  San Diego 
Period  4/01/15 → 6/01/15 
Bibliographical note
Accepted: 9th September 2014Keywords
 cs.DS
 F.2.2; F.1.2
Fingerprint
Dive into the research topics of 'CellProbe Bounds for Online Edit Distance and Other Pattern Matching Problems'. Together they form a unique fingerprint.Profiles

Dr Raphael Clifford
 Department of Computer Science  Reader in Algorithm Design
 Intelligent Systems Laboratory
 Theory and Algorithms
Person: Academic , Member, Group lead