Improved Bounds for Dictionary Look-up with One Error

Gerth Stølting Brodal and Venkatesh Srinivasan

In Information Processing Letters, volume 75(1-2), pages 57-59, 2000.

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(nlog 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. The data structure can be constructed in randomized expected time O(nm).

Copyright notice

Copyright © 2000 by Elsevier Science B.V. All rights reserved.

Online version

ipl00.pdf (150 Kb)

DOI

10.1016/S0020-0190(00)00079-X

BIBTEX entry

@article{ipl00,
  author = "Gerth Stølting Brodal and Venkatesh Srinivasan",
  doi = "10.1016/S0020-0190(00)00079-X",
  issn = "0020-0190",
  journal = "Information Processing Letters",
  number = "1-2",
  pages = "57-59",
  title = "Improved Bounds for Dictionary Look-up with One Error",
  volume = "75",
  year = "2000"
}

Other versions