Name
Abstract | ||
|---|---|---|
We show tight bounds for online Hamming distance computation in the cell-probe model with word size w. The task is to output the Hamming distance between a fixed string of length n and the last n symbols of a stream. We give a lower bound of Ω(δ/w log n) time on average per output, where δ is the number of bits needed to represent an input symbol. We argue that this bound is tight within the model. The lower bound holds under randomisation and amortisation. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.5555/2627817.2627865 | Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
Keywords | DocType | Volume |
algorithms,design,general,theory,numerical algorithms and problems,pattern matching | Conference | abs/1207.1885 |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 3 | 0.40 |
References | Authors | |
23 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Markus Jalsenius | 2 | 87 | 8.93 |
| Benjamin Sach | 3 | 93 | 11.40 |