Name
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 @W(m) bit space lower bounds for L"1, L"2, L"~, 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 @W(m) bit space lower bounds. For other distance functions, we show that there exist space bounds of @W(logm) and O(log^2m) bits. Finally we discuss space lower bounds for non-binary inputs and show how in some cases they can be improved. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2012.06.012 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
online pattern matching,swap distance,present space,space lower bound,bit space lower bound,character class,lower bound,space bound,distance function,different distance measure,online pattern,pattern matching,cross correlation,data structure,sliding window | Journal | 483, |
ISSN | Citations | PageRank |
0304-3975 | 3 | 0.38 |
References | Authors | |
13 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Markus Jalsenius | 2 | 87 | 8.93 |
| ely porat | 3 | 1007 | 79.16 |
| Benjamin Sach | 4 | 93 | 11.40 |