Tight cell-probe bounds for online hamming distance computation

Raphael Clifford; Markus T Jalsenius; Benjamin G Sach

Tight cell-probe bounds for online hamming distance computation

Raphael Clifford
, Markus T Jalsenius
, Benjamin G Sach

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

6 Citations (Scopus)

52 Downloads (Pure)

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 Omege(delta/w log n) time on average per output, where delta 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.

Original language	English
Title of host publication	Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, January 6-8, 2013.
Place of Publication	New Orleans
Publisher	Society for Industrial and Applied Mathematics
Pages	664-674
ISBN (Electronic)	978-1-611972-52-8
Publication status	Published - Jan 2013

Keywords

algorithms
lower bounds
pattern matching
streaming

Access to Document

http://knowledgecenter.siam.org/0236-000129/0236-000129/1

Handle.net

Persistent link

Cite this

Clifford, R., Jalsenius, M. T., & Sach, B. G. (2013). Tight cell-probe bounds for online hamming distance computation. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, January 6-8, 2013. (pp. 664-674). Society for Industrial and Applied Mathematics. http://knowledgecenter.siam.org/0236-000129/0236-000129/1

@inproceedings{b5d8806daa9a476198c4328ec76de196,

title = "Tight cell-probe bounds for online hamming distance computation",

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 Omege(delta/w log n) time on average per output, where delta 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. ",

keywords = "algorithms, lower bounds, pattern matching, streaming",

author = "Raphael Clifford and Jalsenius, \{Markus T\} and Sach, \{Benjamin G\}",

year = "2013",

month = jan,

language = "English",

pages = "664--674",

booktitle = "Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, January 6-8, 2013.",

publisher = "Society for Industrial and Applied Mathematics",

address = "United States",

}

Clifford, R, Jalsenius, MT & Sach, BG 2013, Tight cell-probe bounds for online hamming distance computation. in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, January 6-8, 2013.. Society for Industrial and Applied Mathematics, New Orleans, pp. 664-674. <http://knowledgecenter.siam.org/0236-000129/0236-000129/1>

Tight cell-probe bounds for online hamming distance computation. / Clifford, Raphael; Jalsenius, Markus T; Sach, Benjamin G.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, January 6-8, 2013.. New Orleans: Society for Industrial and Applied Mathematics, 2013. p. 664-674.

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

TY - GEN

T1 - Tight cell-probe bounds for online hamming distance computation

AU - Clifford, Raphael

AU - Jalsenius, Markus T

AU - Sach, Benjamin G

PY - 2013/1

Y1 - 2013/1

N2 - 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 Omege(delta/w log n) time on average per output, where delta 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.

AB - 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 Omege(delta/w log n) time on average per output, where delta 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.

KW - algorithms

KW - lower bounds

KW - pattern matching

KW - streaming

UR - https://www.scopus.com/pages/publications/84876064421

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:84876064421

SP - 664

EP - 674

BT - Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, January 6-8, 2013.

PB - Society for Industrial and Applied Mathematics

CY - New Orleans

ER -

Tight cell-probe bounds for online hamming distance computation

Abstract

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this