Tight Cell-Probe Bounds for Online Hamming Distance Computation
Tight Cell-Probe Bounds for Online Hamming Distance Computation
复制标题
用于在线汉明距离计算的严格单元探针边界
DOI：
10.1137/1.9781611973105.48
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Clifford R
中科院分区：
文献类型：
--
作者：
Clifford R
我们展示了在细胞探针模型与字大小的在线汉明距离计算的紧界。任务是输出固定长度的字符串与流的最后n个符号之间的汉明距离。我们给出了每个输出的平均时间的下限，其中δ是表示输入符号所需的位数。我们认为，这个界限是紧的模型。下限在随机化和摊销下保持不变。
We show tight bounds for online Hamming distance computation in the cell-probe model with word sizew. The task is to output the Hamming distance between a fixed string of lengthnand the lastnsymbols of a stream. We give a lower bound of 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.
登录
查看更多内容
影响因子：
0.5
作者：
KARLOFF, H
通讯作者：
KARLOFF, H
影响因子：
0.5
作者：
Huang, Wei;Shi, Yaoyun;Zhu, Yufan
通讯作者：
Zhu, Yufan
实时字符串匹配
DOI：
10.1145/322234.322244
发表时间：
1981
期刊：
J. ACM
影响因子：
--
作者：
Z. Galil
通讯作者：
Z. Galil
Cell-Probe 模型中在线整数乘法和卷积的下界
影响因子：
--
作者：
R. Clifford;Markus Jalsenius
通讯作者：
Markus Jalsenius
DOI：
10.1137/0207012
发表时间：
1978
期刊：
SIAM J. Comput.
影响因子：
--
作者：
M. Fredman
通讯作者：
M. Fredman