2014/07/24 by Clifford, Raphael, Jalsenius, Markus, Sach, Benjamin
#Data Structures and Algorithms (cs.DS) #F.1.2 #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1407.6559
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 δ-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 Ω((δlog n)/(w+loglog 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 bit-probe model (w=1) with a constant sized input alphabet. We give a lower bound of Ω(√(log n)/(loglog 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 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.