Improved Bounds for Dictionary Look-up with One Error

Gerth Stølting Brodal and Venkatesh Srinivasan

Technical Report, BRICS-RS-99-50, BRICS, Department of Computer Science, Aarhus University, 5 pages, December 1999.

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.

Copyright notice

Copyright © 1999, BRICS, Department of Computer Science, Aarhus University. All rights reserved.

Online version

brics-rs-99-50.pdf (77 Kb)

BIBT_EX entry

@techreport{brics-rs-99-50,
  author = "Gerth Stølting Brodal and Venkatesh Srinivasan",
  institution = "BRICS, Department of Computer Science, Aarhus University",
  issn = "0909-0878",
  month = "December",
  number = "BRICS-RS-99-50",
  pages = "5",
  title = "Improved Bounds for Dictionary Look-up with One Error",
  year = "1999"
}