Dictionary Look-Up with One Error

Let W be a set of n binary strings of length m each. We are interested in designing data structures for W that can answer d-queries quickly; that is, given in a binary string α, decide whether there is any member of W within Hamming distance d of α. The problem, originally raised by Minsky and Papert, remains a challenge in data structure design. In this paper, we make an initial effort toward a theoretical study of the small d case. Our main result is a data structure that achieves O(m log log n) query time with O(nm log m) space for the d = 1 case.