Approximate Dictionary Queries

Gerth Stølting Brodal and Leszek Gasieniec

In Proc. 7th Annual Symposium on Combinatorial Pattern Matching, volume 1075 of Lecture Notes in Computer Science, pages 65-74. Springer Verlag, Berlin, 1996.


Given a set of n binary strings of length m each. We consider the problem of answering d-queries. Given a binary query string α of length m, a d-query is to report if there exists a string in the set within Hamming distance d of α.

We present a data structure of size O(nm) supporting 1-queries in time O(m) and the reporting of all strings within Hamming distance 1 of α in time O(m). The data structure can be constructed in time O(nm). A slightly modified version of the data structure supports the insertion of new strings in amortized time O(m).

Copyright notice

© Springer-Verlag Berlin Heidelberg 1996. All rights reserved.

Online version

cpm96.pdf (197 Kb)



BIBTEX entry

  author = "Gerth St{\o}lting Brodal and Leszek G{\c{a}}sieniec",
  booktitle = "Proc. 7th Annual Symposium on Combinatorial Pattern Matching",
  doi = "10.1007/3-540-61258-0_6",
  isbn = "978-3-540-61258-2",
  pages = "65-74",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Approximate Dictionary Queries",
  volume = "1075",
  year = "1996"