Improved Bounds for Dictionary Look-up with One Error

Gerth Stølting Brodal
Srinivasan Venkatesh

December 1999

Abstract:

Given a dictionary $S$ of $n$ binary strings each of length $m$, we consider the problem of designing a data structure for $S$ that supports $d$-queries; given a binary query string $q$ of length $m$, a $d$-query reports if there exists a string in $S$ within Hamming distance $d$ of $q$. We construct a data structure for the case $d=1$, that requires space $O(n\log m)$ and has query time $O(1)$ in a cell probe model with word size $m$. This generalizes and improves the previous bounds of Yao and Yao for the problem in the bit probe model

Available as PostScript, PDF, DVI.

 

Last modified: 2003-06-08 by webmaster.