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. S., & Venkatesh, S. (1999). Improved Bounds for Dictionary Look-up with One Error. BRICS Report Series, 6(50).