Abstract:
Given a dictionary 
of 
binary strings each of length
, we consider the problem of designing a data structure for that
supports 
-queries; given a binary query string 
of length , a
-query reports if there exists a string in within Hamming distance
of . We construct a data structure for the case 
, that requires space
and has query time 
in a cell probe model with word size
. This generalizes and improves the previous bounds of Yao and Yao for the
problem in the bit probe model
of binary strings each of length
, we consider the problem of designing a data structure for that
supports -queries; given a binary query string of length , a
-query reports if there exists a string in within Hamming distance
of . We construct a data structure for the case , that requires space
and has query time in a cell probe model with word size
. This generalizes and improves the previous bounds of Yao and Yao for the
problem in the bit probe modelAvailable as PostScript, PDF, DVI.