Improved Bounds for Dictionary Look-up with One Error

  • Gerth Stølting Brodal
  • Srinivasan Venkatesh


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

Keywords: Data Structures, Dictionaries, Hashing, Hamming Distance


How to Cite
Brodal, G., & Venkatesh, S. (1999). Improved Bounds for Dictionary Look-up with One Error. BRICS Report Series, 6(50).