Cell-Probe Bounds for Online Edit Distance and Other Pattern Matching Problems

Raphael Clifford, Markus Jalsenius, Benjamin Sach

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

6 Citations (Scopus)
47 Downloads (Pure)

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((\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 bit-probe 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 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.
Original languageEnglish
Title of host publicationACM-SIAM Symposium on Discrete Algorithms
Publication statusPublished - 4 Jan 2015
EventACM-SIAM Symposium on Discrete Algorithms (2015) - San Diego, United States
Duration: 4 Jan 20156 Jan 2015
Conference number: 26

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms (2015)
Abbreviated titleSODA15
CountryUnited States
CitySan Diego
Period4/01/156/01/15

Bibliographical note

Accepted: 9th September 2014

Keywords

  • cs.DS
  • F.2.2; F.1.2

Fingerprint Dive into the research topics of 'Cell-Probe Bounds for Online Edit Distance and Other Pattern Matching Problems'. Together they form a unique fingerprint.

  • Cite this

    Clifford, R., Jalsenius, M., & Sach, B. (2015). Cell-Probe Bounds for Online Edit Distance and Other Pattern Matching Problems. In ACM-SIAM Symposium on Discrete Algorithms