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