Improved Bounds for Dictionary Look-up with One Error

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.

Keywords: Data Structures, Dictionaries, Hashing, Hamming Distance