Improved Bounds for Dictionary Look-up with One Error

  • Gerth Stølting Brodal
  • Srinivasan Venkatesh

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

 

Published
1999-12-20
How to Cite
Brodal, G., & Venkatesh, S. (1999). Improved Bounds for Dictionary Look-up with One Error. BRICS Report Series, 6(50). https://doi.org/10.7146/brics.v6i50.20120