@inproceedings{cb01132ecdde42659e24fe305ffd817f,
title = "Approximate dictionary queries",
abstract = "Given a set of n binary strings of length m each. We consider the problem of answering d-queries. Given a binary query string a of length m, a d-query is to report if there exists a string in the set within Hamming distance α 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).",
author = "Brodal, {Gerth St{\o}lting} and Leszek Gasieniec",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1996.; 7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996 ; Conference date: 10-06-1996 Through 12-06-1996",
year = "1996",
doi = "10.1007/3-540-61258-0_6",
language = "English (US)",
isbn = "3540612580",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "65--74",
editor = "Gene Myers and Dan Hirschberg",
booktitle = "Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings",
}